leetcode

commit c9ad882ab84a9579627a9b1eb7f856f23c3c01e4
parent 624371093e9c6ac8072db39d326e01ff27c86b22
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 19 Feb 2023 19:39:18 +0100

Algorithm II: Day 17

Diffstat:
A
Problems/0583.cpp
 | 
18
++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 19 insertions(+), 0 deletions(-)
diff --git a/Problems/0583.cpp b/Problems/0583.cpp
@@ -0,0 +1,18 @@
+class Solution {
+  vector<vector<int>> dp;
+
+  int solve(const string &s1, const string &s2, int i, int j) {
+    if (i == s1.size() && j == s2.size()) return 0;
+    if (i == s1.size() || j == s2.size())
+      return max(s1.size() - i, s2.size() - j);
+    if (dp[i][j] != INT_MAX) return dp[i][j];
+    if (s1[i] == s2[j]) return solve(s1, s2, i + 1, j + 1);
+    return dp[i][j] = 1 + min(solve(s1, s2, i + 1, j), solve(s1, s2, i, j + 1));
+  }
+
+public:
+  int minDistance(const string &word1, const string &word2) {
+    dp.resize(size(word1) + 1, vector<int>(size(word2) + 1, INT_MAX));
+    return solve(word1, word2, 0, 0);
+  }
+};
diff --git a/README.md b/README.md
@@ -260,6 +260,7 @@ for solving problems.
 |  0566  |    Easy    | [Reshape the Matrix](Problems/0566.cpp)                                                          |
 |  0567  |   Medium   | [Permutation in String](Problems/0567.cpp)                                                       |
 |  0572  |    Easy    | [Subtree of Another Tree](Problems/0572.cpp)                                                     |
+|  0583  |   Medium   | [Delete Operation for Two Strings](Problems/0583.cpp)                                            |
 |  0589  |    Easy    | [N-ary Tree Preorder Traversal](Problems/0589.cpp)                                               |
 |  0590  |    Easy    | [N-ary Tree Postorder Traversal](Problems/0590.cpp)                                              |
 |  0606  |    Easy    | [Construct String from Binary Tree ](Problems/0606.cpp)                                          |