给出两个字符串,找到最长公共子串,并返回其长度。
注意事项
子串的字符应该连续的出现在原字符串中,这与子序列有所不同。
Lintcode上的一道题目,非常经典,需要找到最长的连续公共子串的长度。
因为有两个序列且前后顺序不可以打乱,所以为双序列问题。
这种问题比较重要的是定义状态。这里将状态f[i][j]定义为以A的第i 个字符和B的第j个字符为结尾的最长公共子串的长度。如果A[i-1]!=B[j-1],则f[i][j]=0。
如果A[i-1]==B[j-1],则f[i][j] =f[i-1][j-1]+1。代码如下:
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
res = [[0 for i in xrange(len(B)+1)] for j in xrange(len(A)+1)]
maxlen = 0
for i in xrange(1,len(A)+1):
for j in xrange(1,len(B)+1):
if A[i-1] == B[j-1]:
res[i][j] = res[i-1][j-1]+1
maxlen = max(res[i][j],maxlen)
else:
res[i][j] = 0
return maxlen
时间复杂度O(mn),空间复杂度也为O(mn)。和之前的空间复杂度为O(mn)的题目一样,这题的空间复杂度可以优化为O(min(m,n))甚至是O(1)。O(1)解法是按照对角线和对角线的平行线来扫。
转载于:https://www.cnblogs.com/sherylwang/p/5531366.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)