LintCode 79 [Longest Common Substring]

原题

给出两个字符串，找到最长公共子串，并返回其长度。

样例
给出A=“ABCD”
，B=“CBCE”，返回 2

解题思路

• 典型的双序列行动态规划 - Two Sequence DP
• 不同于Longest Common Subsequence, 本题是substring，string要求是连续的，sequence可以是不连续的
• 本题的状态表示类似于Longest Increasing Subsequence
• cache[i][j]表示string1的前i个字符和string2的前j个字符的LCS，注意必须以i/j结尾

cache

完整代码

class Solution:
    # @param A, B: Two string.
    # @return: the length of the longest common substring.
    def longestCommonSubstring(self, A, B):
        if not A or not B:
            return 0
            
        cache = [[0 for i in range(len(A) + 1)] for i in range(len(B) + 1)]
        
        res = 0
        
        for i in range(1, len(B) + 1):
            for j in range(1, len(A) + 1):
                if A[j - 1] == B[i - 1]:
                    cache[i][j] = cache[i - 1][j - 1] + 1
                res = max(res, cache[i][j])
                
        return res