題目:
?
給定兩個(gè)序列X和Y,返回最長連續(xù)的公共子序列長度。如果沒有連續(xù)公共子序列,返回0.
X和Y的元素都是整數(shù)。
示例:
輸入:
1 5 7 3 4 5
7 3 4 4 5 7 -2
輸出:
3
?說明:
最長的連續(xù)公共子序列是[7,3,4] (X[2:4] 和Y[0:2])
這道題在【leetcode1143】的基礎(chǔ)上增加了公共子序列連續(xù)的限制。解法可以有以下幾種:
題解:
1. 動態(tài)規(guī)劃
創(chuàng)建m+1 行?n+1 列的二維數(shù)組dp,其中?dp[i][j] 表示 a和b分別以a[i-1],b[j-1]結(jié)尾的最長公共子序列的長度。
可以得到狀態(tài)轉(zhuǎn)移方程如下:
最終計(jì)算dp中的最大值即為最長公共連續(xù)子序列的長度。
def findLength(a,b):
m,n=len(a),len(b)
maxlength=0
dp=[[0]*(n+1) for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if a[i-1]==b[j-1]:
dp[i][j]=dp[i-1][j-1]+1
maxlength=max(maxlength,dp[i][j])
return maxlength
時(shí)間復(fù)雜度:O(mn)
空間復(fù)雜度:O(mn),可以優(yōu)化至O(m)或O(n)(只存儲dp矩陣的兩列進(jìn)行計(jì)算)
2. 后綴數(shù)組
def longestCommonSubstring(A, B):
if A == None or B == None:
return
C = [9999]
s = A + C + B
indexOfSharp = len(A)
SA = suffixArray(s)
maxLen, maxIndex = 0, 0
hasCommon = False
for i in range(len(s) - 1):
# 判斷后綴數(shù)組中兩個(gè)相鄰元素對應(yīng)的后綴字符串是否位于“#”兩側(cè),即是否屬于A和B兩個(gè)不同字符串
diff = (SA[i] - indexOfSharp) * (SA[i + 1] - indexOfSharp)
if diff < 0:
tempLen = comlen(s, SA[i], SA[i + 1])
if tempLen > maxLen:
maxLen = tempLen
maxIndex = SA[i]
hasCommon = True
return (maxLen, s[maxIndex:maxIndex + maxLen]) if hasCommon else False
# 得到一個(gè)字符串的后綴數(shù)組
def suffixArray(s):
if s == None or len(s) == 0:
return None
allSuffix = []
for i in range(len(s)):
allSuffix.append([s[i:], i])
sortedList = sorted(allSuffix)
SA = [w[1] for w in sortedList]
return SA
# 比較得到后綴數(shù)組中兩個(gè)相鄰的元素分別對應(yīng)的后綴字符串的最長前綴
def comlen(s, p, q):
j = 0
while j < len(s[p:]) and j < len(s[q:]) and s[p:p + j + 1] == s[q:q + j + 1]:
j += 1
return j
時(shí)間復(fù)雜度:O(nlgn)
空間復(fù)雜度:O(n^2)
3. 哈希表+二分查找
設(shè)最長公共子串的長度為x,那么x在0到min(len(X),len(Y))之間,并且滿足二分的性質(zhì)。因?yàn)槿绻嬖陂L度為m的公共子序列,那么必然存在長度小于m的公共子序列。先哈希一下這兩個(gè)序列,二分長度。每次check的時(shí)候,假設(shè)判斷是否存在長度為k的公共子串,那么看字符串1和字符串2長度為k的子串的哈希值有沒有相同的,如果有返回true,沒有返回false;然后使用二分查找最長公共子串長度x.
def findLen(X, Y):
base, mod = 113, 10**9 + 9
def checkHash(l):
# Construct hash value set of X[0:l]
hx = 0
for i in range(l):
hx = (hx * base + X[i]) % mod
hvx = {hx}
pow_base = pow(base, l - 1, mod)
for i in range(l, len(X)):
hx = ((hx - X[i - l] * pow_base) * base + X[i]) % mod
hvx.add(hx)
# Construct hash value set of Y[0:l] and check whether there is an hash value that matches
hy = 0
for i in range(l):
hy = (hy * base + Y[i]) % mod
if hy in hvx:
return True
for i in range(l, len(Y)):
hy = ((hy - Y[i - l] * pow_base) * base + Y[i]) % mod
if hy in hvx:
return True
return False
# Binary Search
l, r = 0, min(len(X), len(Y))
res = 0
while l <= r:
m = (l + r) // 2
if checkHash(m):
res = m
l = m + 1
else:
r = m - 1
return res
時(shí)間復(fù)雜度:O(nlogn)
空間復(fù)雜度:O(n)文章來源:http://www.zghlxwxcb.cn/news/detail-690525.html
4.雙指針文章來源地址http://www.zghlxwxcb.cn/news/detail-690525.html
def findLength(a, b):
aa = ''.join(a)
l, s = 1, 0
l1, l2 = len(a), len(b)
rtn = 0
while l <= l1 and l+s <= l2:
e = s + l
temp = ''.join(b[s:e])
if temp in aa:
rtn = max(rtn, l)
l += 1
else:
if str(b[e-1]) not in aa:
s = e
else:
s += 1
if s + rtn >= l2:
return rtn
return rtn
到了這里,關(guān)于【python】求最長連續(xù)公共子序列長度的幾種解法的文章就介紹完了。如果您還想了解更多內(nèi)容,請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!