leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0332.cpp (792B)

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