leetcode

commit 923420a4665307da7fe969fb53eac828621a2da8
parent 6a8d64dd6e703ff767604a84452f3a9327b4e209
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 22 Jun 2023 21:18:07 +0200

Improvement to DP problem

Diffstat:
M
Problems/0072.cpp
 | 
22
++++++++++++++++++++++

1 file changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/0072.cpp b/Problems/0072.cpp
@@ -17,3 +17,25 @@ public:
     return dp.back().back();
   }
 };
+
+// Improvement, use two DP arrays instead of a matrix
+class Solution {
+public:
+  int minDistance(const string &word1, const string &word2) {
+    int n = word1.size(), m = word2.size();
+    if (n == 0 || m == 0) return max(m, n);
+    vector<int> dp1(m + 1, 0), dp2(m + 1, 0);
+    iota(dp1.begin(), dp1.end(), 0);
+    for (int i = 1; i <= n; i++) {
+      dp2[0]++;
+      for (int j = 1; j <= m; j++) {
+        if (word1[i - 1] == word2[j - 1])
+          dp2[j] = dp1[j - 1];
+        else
+          dp2[j] = min({dp1[j - 1], dp2[j - 1], dp1[j]}) + 1;
+      }
+      dp1 = dp2;
+    }
+    return dp2[m];
+  }
+};