1436. 旅行终点站

Problem: 1436. 旅行终点站

思路

由于题目数据保证了一定有且仅有一个终点站，而且终点站的性质是不通往其他任意城市，我们只需要用哈希表保存所有在cityB出现的站，然后找出没有出现在cityA中的即可。

复杂度

• 时间复杂度: $O(nm)$：遍历两次数组。其中n是paths的长度，m是字符串的长度。
• 空间复杂度: $O(nm)$：哈希表。

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> s = new HashSet<>();
        int n = paths.size();
        for (int i = 0; i < n; i++) {
            s.add(paths.get(i).get(0));
        }
        for (int i = 0; i < n; i++) {
           if (!s.contains(paths.get(i).get(1))) return paths.get(i).get(1);
        }
        return "";
    }
}