yamxxopd
yndfyamxx
Output: 5我不太確定如何找到兩個(gè)字符串之間最多共享字符的數(shù)量。例如（上面的字符串）最多共享的字符是“yamxx”，它有 5 個(gè)字符長。xx 不是一個(gè)解決方案，因?yàn)檫@不是最大數(shù)量的共享字符。在本例中，最多的是 yamxx，它有 5 個(gè)字符長，因此輸出將為 5。我對(duì) python 和堆棧溢出很陌生，所以任何幫助將不勝感激！注意：兩個(gè)字符串中的順序應(yīng)該相同
3 回答
HUX布斯
TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超6個(gè)贊
這是使用動(dòng)態(tài)規(guī)劃的簡單、有效的解決方案。
def longest_subtring(X, Y):
m,n = len(X), len(Y)
LCSuff = [[0 for k in range(n+1)] for l in range(m+1)]
result = 0
for i in range(m + 1):
for j in range(n + 1):
if (i == 0 or j == 0):
LCSuff[i][j] = 0
elif (X[i-1] == Y[j-1]):
LCSuff[i][j] = LCSuff[i-1][j-1] + 1
result = max(result, LCSuff[i][j])
else:
LCSuff[i][j] = 0
print (result )
longest_subtring("abcd", "arcd") # prints 2
longest_subtring("yammxdj", "nhjdyammx") # prints 5
BIG陽
TA貢獻(xiàn)1859條經(jīng)驗(yàn) 獲得超6個(gè)贊
該解決方案從盡可能長的子串開始。如果對(duì)于某個(gè)長度，沒有該長度的匹配子字符串，則它會(huì)移動(dòng)到下一個(gè)較低的長度。這樣，它可以在第一次成功匹配時(shí)停止。
s_1 = "yamxxopd"
s_2 = "yndfyamxx"
l_1, l_2 = len(s_1), len(s_2)
found = False
sub_length = l_1 # Let's start with the longest possible sub-string
while (not found) and sub_length: # Loop, over decreasing lengths of sub-string
for start in range(l_1 - sub_length + 1): # Loop, over all start-positions of sub-string
sub_str = s_1[start:(start+sub_length)] # Get the sub-string at that start-position
if sub_str in s_2: # If found a match for the sub-string, in s_2
found = True # Stop trying with smaller lengths of sub-string
break # Stop trying with this length of sub-string
else: # If no matches found for this length of sub-string
sub_length -= 1 # Let's try a smaller length for the sub-strings
print (f"Answer is {sub_length}" if found else "No common sub-string")
輸出：
答案是5
SMILET
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊
s1 = "yamxxopd"
s2 = "yndfyamxx"
# initializing counter
counter = 0
# creating and initializing a string without repetition
s = ""
for x in s1:
if x not in s:
s = s + x
for x in s:
if x in s2:
counter = counter + 1
# display the number of the most amount of shared characters in two strings s1 and s2
print(counter) # display 5
添加回答
舉報(bào)
0/150
提交
取消