4C++ Set difference|recursive DFS|Sort+binary search|Trie||3ms Beats 99.28%
Intuition\n Describe your first thoughts on how to solve this problem. \nIn fact, more than 4 different solutions are tried. 4 of them are presented & very diff
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn fact, more than 4 different solutions are tried. 4 of them are presented & very different.\n\nUse hash table `unordered_set<string>`  to implement Set difference.\nThis approach is fast,runs in 3ms & Beats 99.28%.\n\n2nd approach uses a recursive DFS implementation which is fast, runs in 4ms & beats 96.89%!!!!\n\nIn the DFS approach, construct `unordered_map<string, string> edge` to store the info on directed edges in paths.\n\n3rd approach doesn\'t use any hash table, and uses sorting & binary search which is not slow & runs in 6ms.\n\n4th solution uses Trie class.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThanks to the suggestion of @sergei99, the revised code is basically the implementation for the Set difference operation\n$$\np=\\{e[1]: e\\in paths\\}\\setminus \\{e[0]: e\\in paths\\}\n$$\nAt final $p$ has only 1 element.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# revised easy Code runs in 3ms Beats 99.28%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        unordered_set<string> p;\n        for(auto& e: paths)\n            p.insert(e[1]);\n        for(auto& e: paths)\n            p.erase(e[0]);\n        return *p.begin(); \n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Code using recursive DFS 4 ms Beats 96.89%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    string dfs(string v, unordered_map<string, string>& edge){\n        if (edge.count(v)==0) return v;\n        return dfs(edge[v], edge);\n    }\n    string destCity(vector<vector<string>>& paths) {\n        unordered_map<string, string> edge;\n        for(auto& e:paths){\n           edge[e[0]]=e[1];\n        }\n        return move(dfs(paths[0][0], edge));\n    }\n};\n\n```\n# Code using Sort+ Binary Search\n\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        const int n = paths.size();\n        string s[n], e[n];\n\n        for(int i = 0; i < n; i++) {\n            s[i] = paths[i][0];\n            e[i] = paths[i][1];\n        }\n        sort(s, s+n);\n        sort(e, e+n);\n        int search=0;\n        for (int i = 0; i < n; i++) {\n            string x = e[i];\n            search=lower_bound(s+search, s+n, x)-s;\n\n            if (search == n || s[search] != x) \n                return move(x);\n        }\n        return NULL; \n    }\n};\n\n```\n# Code using Trie class\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Trie {\npublic:\n    bool isEnd = 0;\n    array<Trie*, 64> links = {};\n\n    Trie() {}\n\n    ~Trie() {\n    //    cout<<"destructor\\n";\n        for (auto link : links) {\n            if (link) \n                delete link;\n        }\n    }\n\n    void insert(string& word) {\n        Trie* node = this;\n        for (char c : word) {\n            unsigned i = c&63;\n            if (node->links[i] == NULL) {\n                node->links[i] = new Trie();\n            }\n            node = node->links[i];\n        }\n        node->isEnd = 1;\n    }\n\n    bool search(string& word) {\n        Trie* Node = this;\n        for(char c : word){\n            int i = c & 63;\n            if(Node->links[i]==NULL) return 0;\n            Node = Node->links[i];\n        }\n        return Node->isEnd;  \n    }\n};\nclass Solution {\npublic:\n    string destCity(vector<vector<string>>& paths) {\n        Trie* root =new Trie();\n        int n=paths.size();\n        for(int i = 0; i <n; i++){\n            root->insert(paths[i][0]);\n        }\n        for(int i = 0; i < n; i++){\n            string x=paths[i][1];\n            if(!root->search(x)){\n                delete root;\n                return x;\n            }\n        }\n        return NULL; \n    }\n};\n```
['Hash Table', 'Binary Search', 'Depth-First Search', 'Trie', 'Recursion', 'Sorting', 'C++']