1436. Destination City

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, string> mp;
        string ret;
        for(auto path:paths)
        {
            mp[path[0]] = path[1];
        }
        
        string city = paths[0][0];
        while(mp.find(city)!=mp.end())
        {
            ret = mp[city];
            city = mp[city];
        }
        return ret;
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)