题解 | #最长公共子串#
最长公共子串
http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
def LCS(self , str1 , str2 ):
#动态规划
m,n=len(str1),len(str2)
maxLen,endIndex=0,0
dp=[[0 for t in range(n)] for x in range(m)]
for i in range(m):
for j in range(n):
if str1[i]==str2[j]:
if i==0 or j==0:dp[i][j]=1
else:dp[i][j]=dp[i-1][j-1]+1
if dp[i][j]>maxLen:
endIndex=i
maxLen=dp[i][j]
else:dp[i][j]=0
return str1[endIndex-maxLen+1:endIndex+1]
投递美团等公司10个岗位 >
