leetcode

commit 649c5efa45d933d4816951d94df6022586ccc15a
parent ebf57653ad2c6081cb9b018ec634e7b5641cb1f8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 27 Apr 2024 14:15:58 +0200

Daily Problem

Diffstat:
A
Problems/0514.cpp
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/0514.cpp b/Problems/0514.cpp
@@ -0,0 +1,44 @@
+class Solution {
+    static int left[101][26];
+    static int right[101][26];
+    static int dp[101][101];
+
+    int rec(const string &ring, const string &key, int idx, int crnt) {
+        if (idx == size(key)) return 0;
+
+        if (key[idx] == ring[crnt]) return 1 + rec(ring, key, idx + 1, crnt);
+        if (dp[idx][crnt] != -1) return dp[idx][crnt];
+
+        const int n = size(ring);
+        const int l = left[crnt][key[idx] - 'a'];
+        const int r = right[crnt][key[idx] - 'a'];
+
+        return dp[idx][crnt] = 1 + min(l + rec(ring, key, idx + 1, (crnt - l + n) % n),
+                                       r + rec(ring, key, idx + 1, (crnt + r) % n));
+    }
+
+  public:
+    int findRotateSteps(const string &ring, const string &key) {
+        const int n = size(ring);
+
+        memset(dp, 0xFF, sizeof(dp));
+        memset(left, 0x00, sizeof(left));
+        memset(right, 0x00, sizeof(right));
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 1; j < n; j++) {
+                const int x = ring[(i + j) % n] - 'a';
+                const int y = ring[(i + n - j) % n] - 'a';
+
+                if (!right[i][x]) right[i][x] = j;
+                if (!left[i][y]) left[i][y] = j;
+            }
+        }
+
+        return rec(ring, key, 0, 0);
+    }
+};
+
+int Solution::left[101][26];
+int Solution::right[101][26];
+int Solution::dp[101][101];
diff --git a/README.md b/README.md
@@ -362,6 +362,7 @@ for solving problems.
 |  0509  |    Easy    | [Fibonacci Number](Problems/0509.cpp)                                                              |
 |  0511  |    Easy    | [Game Play Analysis I](Problems/0511.cpp)                                                          |
 |  0513  |   Medium   | [Find Bottom Left Tree Value](Problems/0513.cpp)                                                   |
+|  0514  |    Hard    | [Freedom Trail](Problems/0514.cpp)                                                                 |
 |  0515  |   Medium   | [Find Largest Value in Each Tree Row](Problems/0515.cpp)                                           |
 |  0516  |   Medium   | [Longest Palindromic Subsequence](Problems/0516.cpp)                                               |
 |  0518  |   Medium   | [Coin Change II](Problems/0518.cpp)                                                                |