编辑距离

yingl · yingl · commit 6674f040d6dd · 2016-08-14T14:08:31.000+08:00
diff --git a/edit_distance.py b/edit_distance.py
@@ -0,0 +1,25 @@
+# -*- coding: utf-8 -*-
+
+class Solution: 
+    # @param word1 & word2: Two string.
+    # @return: The minimum number of steps.
+    def minDistance(self, word1, word2):
+        # write your code here
+        self.cache = [[-1] * len(word2) for i in xrange(len(word1))]
+        return self._minDistance(word1, 0, word2, 0)
+
+    def _minDistance(self, word_1, start_1, word_2, start_2):
+        if start_1 >= len(word_1):
+            return len(word_2) - start_2
+        elif start_2 >= len(word_2):
+            return len(word_1) - start_1
+        if self.cache[start_1][start_2] == -1:
+            # 假设通过插入一个与另一方相同位置一样的字符
+            dist_1 = 1 + min(self._minDistance(word_1, start_1 + 1, word_2, start_2), \
+                      self._minDistance(word_1, start_1, word_2, start_2 + 1))
+            # 相同位置如果不同，做一次字符改变，继续处理后面的字符串。
+            dist_2 = self._minDistance(word_1, start_1 + 1, word_2, start_2 + 1)
+            if word_1[start_1] != word_2[start_2]:
+                dist_2 += 1
+            self.cache[start_1][start_2] = min(dist_1, dist_2)
+        return self.cache[start_1][start_2]
