feat: add dynamic programming algorithm to strings.min_distance.py (keon#838)

psalqvist · Philip Salqvist · web-flow · commit c0e5404a3303 · 2023-03-08T01:35:29.000-08:00
also added a small unit test to ensure the algorithm is correct fixes: keon#15 Co-authored-by: Philip Salqvist <philipsalqvist@MacBook-Pro-som-tillhor-Philip.local>
diff --git a/algorithms/strings/min_distance.py b/algorithms/strings/min_distance.py
@@ -12,17 +12,51 @@
 """
 
 def min_distance(word1, word2):
+    """
+    Finds minimum distance by getting longest common subsequence
+
+    :type word1: str
+    :type word2: str
+    :rtype: int
+    """
     return len(word1) + len(word2) - 2 * lcs(word1, word2, len(word1), len(word2))
 
-def lcs(s1, s2, i, j):
+def lcs(word1, word2, i, j):
     """
-    The length of longest common subsequence among the two given strings s1 and s2
+    The length of longest common subsequence among the two given strings word1 and word2
     """
     if i == 0 or j == 0:
         return 0
-    elif s1[i - 1] == s2[j - 1]:
-        return 1 + lcs(s1, s2, i - 1, j - 1)
+    if word1[i - 1] == word2[j - 1]:
+        return 1 + lcs(word1, word2, i - 1, j - 1)
+    return max(lcs(word1, word2, i - 1, j), lcs(word1, word2, i, j - 1))
+
+def min_distance_dp(word1, word2):
+    """
+    Finds minimum distance in a dynamic programming manner
+    TC: O(length1*length2), SC: O(length1*length2)
+
+    :type word1: str
+    :type word2: str
+    :rtype: int
+    """
+    length1, length2 = len(word1)+1, len(word2)+1
+    res = [[0 for _ in range(length2)] for _ in range(length1)]
+
+    if length1 == length2:
+        for i in range(1, length1):
+            res[i][0], res[0][i] = i, i
     else:
-        return max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1))
+        for i in range(length1):
+            res[i][0] = i
+        for i in range(length2):
+            res[0][i] = i
+
+    for i in range(1, length1):
+        for j in range(1, length2):
+            if word1[i-1] == word2[j-1]:
+                res[i][j] = res[i-1][j-1]
+            else:
+                res[i][j] = min(res[i-1][j], res[i][j-1]) + 1
 
-# TODO: Using dynamic programming
+    return res[len(word1)][len(word2)]
diff --git a/tests/test_strings.py b/tests/test_strings.py
@@ -32,6 +32,7 @@
     repeat_string,
     text_justification,
     min_distance,
+    min_distance_dp,
     longest_common_prefix_v1, longest_common_prefix_v2,
     longest_common_prefix_v3,
     rotate, rotate_alt,
@@ -535,6 +536,13 @@ class TestMinDistance(unittest.TestCase):
     def test_min_distance(self):
         self.assertEqual(2, min_distance("sea", "eat"))
         self.assertEqual(6, min_distance("abAlgocrithmf", "Algorithmmd"))
+        self.assertEqual(4, min_distance("acbbd", "aabcd"))
+
+class TestMinDistanceDP(unittest.TestCase):
+    def test_min_distance(self):
+        self.assertEqual(2, min_distance_dp("sea", "eat"))
+        self.assertEqual(6, min_distance_dp("abAlgocrithmf", "Algorithmmd"))
+        self.assertEqual(4, min_distance("acbbd", "aabcd"))
 
 
 class TestLongestCommonPrefix(unittest.TestCase):
