最长公共子序列

yingl · yingl · commit afd4aceee0d5 · 2016-08-14T10:24:52.000+08:00
diff --git a/longest_common_subsequence.py b/longest_common_subsequence.py
@@ -0,0 +1,28 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param A, B: Two strings.
+    @return: The length of longest common subsequence of A and B.
+    """
+    def longestCommonSubsequence(self, A, B):
+        # write your code here
+        self.ret = 0
+        self.cache = [[-1] * len(A) for i in xrange(len(B))]  # 缓存，避免重复计算
+        self._longestCommonSubsequence(A, B, 0, 0)
+        return self.ret
+
+    def _longestCommonSubsequence(self, A, B, start_a, start_b):
+        if (start_a >= len(A)) or (start_b >= len(B)):
+            return 0
+        elif self.cache[start_a][start_b] == -1:
+            if A[start_a] != B[start_b]:
+                len_a = self._longestCommonSubsequence(A, B, start_a + 1, start_b)
+                len_b = self._longestCommonSubsequence(A, B, start_a, start_b + 1)
+                self.ret = max(max(len_a, len_b), self.ret) # LCS不要求连续
+                self.cache[start_a][start_b] = max(len_a, len_b)
+            else:
+                _len = self._longestCommonSubsequence(A, B, start_a + 1, start_b + 1)
+                self.ret = max(_len + 1, self.ret)
+                self.cache[start_a][start_b] = _len + 1
+        return self.cache[start_a][start_b]
