如何找到两个字符串中最多共享字符？

Question

yamxxopd yndfyamxx Output: 5我不太确定如何找到两个字符串之间最多共享字符的数量。例如（上面的字符串）最多共享的字符是“yamxx”，它有 5 个字符长。xx 不是一个解决方案，因为这不是最大数量的共享字符。在本例中，最多的是 yamxx，它有 5 个字符长，因此输出将为 5。我对 python 和堆栈溢出很陌生，所以任何帮助将不胜感激！注意：两个字符串中的顺序应该相同

Answer 1

这是使用动态规划的简单、有效的解决方案。

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

Answer 2

该解决方案从尽可能长的子串开始。如果对于某个长度，没有该长度的匹配子字符串，则它会移动到下一个较低的长度。这样，它可以在第一次成功匹配时停止。

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

Answer 3

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