LintCode Q79 Longest Common Substring in Python

  • Jinhai ZHOU
  • 5 Minutes
  • 2016年12月17日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
# @param A, B: Two string.
# @return: the length of the longest common substring.
def longestCommonSubstring(self, A, B):
# write your code here
# dynamic programming
length = 0
if len(A) == 0 or len(B) == 0:
return 0
n, m = len(A), len(B)
dp = [[0]*n for i in xrange(m)]
# initialisation
if A[0] == B[0]:
dp[0][0] = 1
length = 1
else:
dp[0][0] = 0
for i in xrange(1, n):
if A[i] == B[0]:
dp[0][i] = 1
length = 1
else:
dp[0][i] = 0
for i in xrange(1, m):
if A[0] == B[i]:
dp[i][0] = 1
length = 1
else:
dp[i][0] = 0
for row in xrange(1, m):
for col in xrange(1, n):
if B[row] == A[col]:
dp[row][col] = 1 + dp[row - 1][col - 1]
length = max(dp[row][col], length)
else:
dp[row][col] = 0
return length
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。