题目描述

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityA_i, cityB_i] 表示该线路将会从 cityA_i 直接前往 cityB_i 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

样例

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo"。
本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo"。

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A"。

输入：paths = [["A","Z"]]
输出："Z"

限制

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityA_i.length, cityB_i.length <= 10
• cityA_i != cityB_i
• 所有字符串均由大小写英文字母和空格字符组成。

算法

(哈希表) $O(n)$

1. 首先遍历一遍数组，将所有 cityA_i 加入哈希表。
2. 再遍历一遍数组，如果发现 cityB_i 不在哈希表中，则返回该城市。

时间复杂度

• 遍历两次数组，哈希表的操作时间复杂度近似为字符串的长度，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储哈希表。

C++ 代码

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> s;

        for (const auto &v : paths)
            s.insert(v[0]);

        for (const auto &v : paths)
            if (s.find(v[1]) == s.end())
                return v[1];

        return "";
    }
};