給定兩個字符串，找到兩個字符串之間從左到右順序相同的公共字符。實施例1string_1 = 'hcarry'string_2 = 'sallyc'Output - 'ay'實施例2string_1 = 'jenny'string_2 = 'ydjeu'Output - 'je'示例 1 的解釋 -string_1和之間的常見字符string_2是 c、a、y。但由于c位于ayin之前string_1 和之后，我們不會考慮輸出中的ay字符。兩個字符串之間的公共字符的順序必須保持并且必須相同。string_2c示例 2 的解釋 -string_1和之間的公共字符string_2是 j、e、y。但由于y位于jein之前string_2 和之后，我們不會考慮輸出中的je字符。兩個字符串之間的公共字符的順序必須保持并且必須相同。string_1y我的做法——查找字符串之間的公共字符，然后將其存儲在每個單獨(dú)字符串的另一個變量中。Example - string_1 = 'hcarry'string_2 = 'sallyc'Common_characters = c,a,ystring_1_com = caystring_2_com = ayc我使用sorted, counter, enumerate函數(shù)來進(jìn)入string_1_com and string_2_com Python?，F(xiàn)在找到 之間的最長公共子序列string_1_com and string_2_com 。您將得到輸出作為結(jié)果。這是蠻力解決方案。對此的最佳解決方案是什么？
4 回答
慕容森
TA貢獻(xiàn)1853條經(jīng)驗 獲得超18個贊
在我的書中，這種算法被稱為字符串匹配。它的運(yùn)行時間復(fù)雜度為 O( mn )，其中m和n是字長。我想它也可以在完整的單詞上運(yùn)行，最有效的方法取決于預(yù)期的常見字母數(shù)量以及如何執(zhí)行排序和過濾。我將針對常見字母字符串進(jìn)行解釋，因為這樣更容易。
這個想法是，您查看(m+1) * (n+1)個節(jié)點(diǎn)的有向無環(huán)圖。通過該圖的每條路徑（從左上到右下）代表了匹配單詞的獨(dú)特方式。我們想要匹配字符串，并-在單詞中添加空格 ( )，以便它們與最多的常見字母對齊。例如cay和的最終狀態(tài)ayc是
cay-
-ayc
每個節(jié)點(diǎn)存儲其代表的部分匹配的最大匹配數(shù)，并且在算法結(jié)束時，結(jié)束節(jié)點(diǎn)將為我們提供最大匹配數(shù)。
我們從左上角開始，那里沒有任何東西匹配，所以這里有 0 個匹配的字母（得分 0）。
c a y
0 . . .
a . . . .
y . . . .
c . . . .
我們將遍歷該圖，并使用先前節(jié)點(diǎn)的數(shù)據(jù)為每個節(jié)點(diǎn)計算匹配字母的最大數(shù)量。
節(jié)點(diǎn)從左->右、上->下以及對角從左上->右-下連接。
向右移動代表使用 中的一個字母cay并將我們到達(dá)的字母與-插入的字母相匹配ayc。
向下移動代表相反的情況（從 消耗ayc并插入-到cay）。
對角線移動表示消耗每個單詞中的一個字母并匹配它們。
查看起始節(jié)點(diǎn)右側(cè)的第一個節(jié)點(diǎn)，它表示匹配
c
-
并且這個節(jié)點(diǎn)（顯然）只能從起始節(jié)點(diǎn)到達(dá)。
第一行和第一列中的所有節(jié)點(diǎn)都將為 0，因為它們都表示與相同數(shù)量的 匹配的一個或多個字母-。
我們得到圖表
c a y
0 0 0 0
a 0 . . .
y 0 . . .
c 0 . . .
這就是設(shè)置，現(xiàn)在有趣的部分開始了。
查看第一個未評估的節(jié)點(diǎn)，它表示將子字符串c與匹配a，我們想要決定如何以最多數(shù)量的匹配字母到達(dá)那里。
替代方案 1：我們可以從左邊的節(jié)點(diǎn)到達(dá)那里。左邊的節(jié)點(diǎn)代表匹配
-
a
因此，通過選擇這條路徑到達(dá)當(dāng)前節(jié)點(diǎn)，我們到達(dá)
-c
a-
匹配c給-我們沒有正確的匹配，因此該路徑的分?jǐn)?shù)是 0（取自最后一個節(jié)點(diǎn)）加上 0（c/-剛剛進(jìn)行的匹配的分?jǐn)?shù)）。所以這條路徑的 0 + 0 = 0。
方案2：我們可以從上面到達(dá)這個節(jié)點(diǎn)，這條路徑代表從
c -> c-
- -a
這也給我們 0 分。此項得分為 0。
替代方案 3：我們可以從左上角到達(dá)該節(jié)點(diǎn)。這是從起始節(jié)點(diǎn)（什么都沒有）轉(zhuǎn)變?yōu)橄拿總€字母中的一個字符。那就是匹配
c
a
由于c和a是不同的字母，因此這條路徑也得到 0 + 0 = 0。
c a y
0 0 0 0
a 0 0 . .
y 0 . . .
c 0 . . .
但對于下一個節(jié)點(diǎn)來說，它看起來更好。我們?nèi)匀豢梢钥紤]三種選擇。替代方案 1 和 2 總是給我們 0 額外分，因為它們總是表示將字母與 匹配-，因此這些路徑將為我們提供 0 分。讓我們繼續(xù)討論替代方案 3。
對于我們當(dāng)前的節(jié)點(diǎn)，對角移動意味著從
c -> ca
- -a
這是一場比賽！
這意味著有一條通往該節(jié)點(diǎn)的路徑為我們提供了 1 分。我們?nèi)拥?0 并保留 1。
c a y
0 0 0 0
a 0 0 1 .
y 0 . . .
c 0 . . .
對于這一行的最后一個節(jié)點(diǎn)，我們查看了三個替代方案，并意識到我們不會獲得任何新點(diǎn)（新匹配），但我們可以使用之前的 1 點(diǎn)路徑到達(dá)該節(jié)點(diǎn)：
ca -> cay
-a -a-
所以這個節(jié)點(diǎn)的score也是1。
對所有節(jié)點(diǎn)執(zhí)行此操作，我們得到以下完整圖表
c a y
0 0 0 0
a 0 0 1 1
y 0 0 1 2
c 0 1 1 2
分?jǐn)?shù)唯一增加的地方來自于
c -> ca | ca -> cay | - -> -c
- -a | -a -ay | y yc
所以結(jié)束節(jié)點(diǎn)告訴我們最大匹配是 2 個字母。由于在您的情況下您希望知道得分為 2 的最長路徑，因此您還需要跟蹤每個節(jié)點(diǎn)所采用的路徑。
該圖很容易實現(xiàn)為矩陣（或數(shù)組的數(shù)組）。
我建議您作為元素使用tuple帶有一個score元素和一個path元素的 a ，并且在路徑元素中您只存儲對齊字母，那么最終矩陣的元素將是
c a y
0 0 0 0
a 0 0 (1, a) (1, a)
y 0 0 (1, a) (2, ay)
c 0 (1, c) (1, a/c) (2, ay)
在我注意到的一處a/c，這是因為 stringca和ayc具有兩個不同的最大長度子序列。您需要決定在這些情況下該怎么做，要么只選擇其中一個，要么保留兩者。
編輯：
這是此解決方案的實現(xiàn)。
def longest_common(string_1, string_2):
len_1 = len(string_1)
len_2 = len(string_2)
m = [[(0,"") for _ in range(len_1 + 1)] for _ in range(len_2 + 1)] # intitate matrix
for row in range(1, len_2+1):
for col in range(1, len_1+1):
diag = 0
match = ""
if string_1[col-1] == string_2[row-1]: # score increase with one if letters match in diagonal move
diag = 1
match = string_1[col - 1]
# find best alternative
if m[row][col-1][0] >= m[row-1][col][0] and m[row][col-1][0] >= m[row-1][col-1][0]+diag:
m[row][col] = m[row][col-1] # path from left is best
elif m[row-1][col][0] >= m[row-1][col-1][0]+diag:
m[row][col] = m[row-1][col] # path from above is best
else:
m[row][col] = (m[row-1][col-1][0]+diag, m[row-1][col-1][1]+match) # path diagonally is best
return m[len_2][len_1][1]
>>> print(longest_common("hcarry", "sallyc"))
ay
>>> print(longest_common("cay", "ayc"))
ay
>>> m
[[(0, ''), (0, ''), (0, ''), (0, '')],
[(0, ''), (0, ''), (1, 'a'), (1, 'a')],
[(0, ''), (0, ''), (1, 'a'), (2, 'ay')],
[(0, ''), (1, 'c'), (1, 'c'), (2, 'ay')]]
森林海
TA貢獻(xiàn)2011條經(jīng)驗 獲得超2個贊
這是該問題的一個簡單的、基于動態(tài)規(guī)劃的實現(xiàn)：
def lcs(X, Y):
m, n = len(X), len(Y)
L = [[0 for x in xrange(n+1)] for x in xrange(m+1)]
# using a 2D Matrix for dynamic programming
# L[i][j] stores length of longest common string for X[0:i] and Y[0:j]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
# Following code is used to find the common string
index = L[m][n]
# Create a character array to store the lcs string
lcs = [""] * (index+1)
lcs[index] = ""
# Start from the right-most-bottom-most corner and
# one by one store characters in lcs[]
i = m
j = n
while i > 0 and j > 0:
# If current character in X[] and Y are same, then
# current character is part of LCS
if X[i-1] == Y[j-1]:
lcs[index-1] = X[i-1]
i-=1
j-=1
index-=1
# If not same, then find the larger of two and
# go in the direction of larger value
elif L[i-1][j] > L[i][j-1]:
i-=1
else:
j-=1
print ("".join(lcs))
阿波羅的戰(zhàn)車
TA貢獻(xiàn)1862條經(jīng)驗 獲得超6個贊
更簡單的解決方案-----謝謝！
def f(s, s1):
cc = list(set(s) & set(s1))
ns = ''.join([S for S in s if S in cc])
ns1 = ''.join([S for S in s1 if S in cc])
found = []
b = ns[0]
for e in ns[1:]:
cs = b+e
if cs in ns1:
found.append(cs)
b = e
return found
慕慕森
TA貢獻(xiàn)1856條經(jīng)驗 獲得超17個贊
但是..您已經(jīng)知道術(shù)語“最長公共子序列”并且可以找到大量動態(tài)規(guī)劃算法的描述。
偽代碼
function LCSLength(X[1..m], Y[1..n])
? ? C = array(0..m, 0..n)
? ? for i := 0..m
? ? ? ? C[i,0] = 0
? ? for j := 0..n
? ? ? ? C[0,j] = 0
? ? for i := 1..m
? ? ? ? for j := 1..n
? ? ? ? ? ? if X[i] = Y[j] //i-1 and j-1 if reading X & Y from zero
? ? ? ? ? ? ? ? C[i,j] := C[i-1,j-1] + 1
? ? ? ? ? ? else
? ? ? ? ? ? ? ? C[i,j] := max(C[i,j-1], C[i-1,j])
? ? return C[m,n]
function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
? ? if i = 0 or j = 0
? ? ? ? return ""
? ? if? X[i] = Y[j]
? ? ? ? return backtrack(C, X, Y, i-1, j-1) + X[i]
? ? if C[i,j-1] > C[i-1,j]
? ? ? ? return backtrack(C, X, Y, i, j-1)
? ? return backtrack(C, X, Y, i-1, j)
添加回答
舉報
0/150
提交
取消