leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0332.cpp (792B)

      1 class Solution {
      2     vector<string> res;
      3     int n;
      4 
      5     typedef unordered_map<string, map<string, int>> adj_t;
      6     bool rec(adj_t &adj) {
      7         if (res.size() == n) return true;
      8 
      9         const string &name = res.back();
     10         for (auto &next : adj[name]) {
     11             if (!next.second) continue;
     12             res.push_back(next.first);
     13             next.second--;
     14             if (rec(adj)) return true;
     15             next.second++;
     16             res.pop_back();
     17         }
     18         return false;
     19     }
     20 
     21   public:
     22     vector<string> findItinerary(const vector<vector<string>> &tickets) {
     23         adj_t adj;
     24 
     25         n = tickets.size() + 1;
     26         for (const auto &ticket : tickets)
     27             adj[ticket[0]][ticket[1]]++;
     28 
     29         res = {"JFK"};
     30         rec(adj);
     31         return res;
     32     }
     33 };