lintcode 79. 最长公共子串

难度：中等

1. Description

79. 最长公共子串

2. Solution

动态规划入门题

思路

• python3

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

3. Reference

1. https://www.lintcode.com/problem/longest-common-substring/description