c++ 29ms solution


  • 0

    brute force dfs search ...

    class Solution {
     private:
      bool DFS(unordered_map<string, vector<pair<string, bool>>>& dic,
               vector<string>& ans, string& cur, int size) {
        ans.push_back(cur);
        for (auto& x : dic[cur])
          if (!x.second) {
            x.second = true;
            cur = x.first;
            if (DFS(dic, ans, cur, size)) return true;
            x.second = false;
          }
    
        if (ans.size() == size) return true;
    
        ans.pop_back();
        return false;
      }
    
     public:
      vector<string> findItinerary(vector<pair<string, string>> tickets) {
        unordered_map<string, vector<pair<string, bool>>> dic;
        for (auto& t : tickets) dic[t.first].push_back(make_pair(t.second, false));
        for (auto& x : dic) sort(x.second.begin(), x.second.end());
        string cur = "JFK";
        vector<string> ans;
        DFS(dic, ans, cur, tickets.size() + 1);
        return ans;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.