leetcode

commit 84a63246906afd2594eeed91f3efbbce09cf4c0e
parent f3dd448170fbc76bf48655c58dc9f0d75551ea75
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 14 Sep 2023 21:19:27 +0200

Daily Problem

Diffstat:
A
Problems/0332.cpp
 | 
33
+++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 34 insertions(+), 0 deletions(-)
diff --git a/Problems/0332.cpp b/Problems/0332.cpp
@@ -0,0 +1,33 @@
+class Solution {
+    vector<string> res;
+    int n;
+
+    typedef unordered_map<string, map<string, int>> adj_t;
+    bool rec(adj_t &adj) {
+        if (res.size() == n) return true;
+
+        const string &name = res.back();
+        for (auto &next : adj[name]) {
+            if (!next.second) continue;
+            res.push_back(next.first);
+            next.second--;
+            if (rec(adj)) return true;
+            next.second++;
+            res.pop_back();
+        }
+        return false;
+    }
+
+  public:
+    vector<string> findItinerary(const vector<vector<string>> &tickets) {
+        adj_t adj;
+
+        n = tickets.size() + 1;
+        for (const auto &ticket : tickets)
+            adj[ticket[0]][ticket[1]]++;
+
+        res = {"JFK"};
+        rec(adj);
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -245,6 +245,7 @@ for solving problems.
 |  0322  |   Medium   | [Coin Change](Problems/0322.cpp)                                                                   |
 |  0326  |    Easy    | [Power of Three](Problems/0326.cpp)                                                                |
 |  0328  |   Medium   | [Odd Even Linked List](Problems/0328.cpp)                                                          |
+|  0332  |    Hard    | [Reconstruct Itinerary](Problems/0332.cpp)                                                         |
 |  0334  |   Medium   | [Increasing Triplet Subsequence](Problems/0334.cpp)                                                |
 |  0338  |    Easy    | [Counting Bits](Problems/0338.cpp)                                                                 |
 |  0342  |    Easy    | [Power of Four](Problems/0342.cpp)                                                                 |