如何使用Python计算两个单词中按顺序相同的公共字母数量？

Question

我有一个字符串 pizzas，与 pizza 进行比较时，它们是不同的。如何编写一个程序来计算两个单词之间按顺序相同的公共字母数量，并且如果匹配度达到60％，则变量 match 就是 True？

例如，pizz 和 pizzas 有6个字母中的4个是相同的，这是一个66％的匹配，这意味着 match 必须是 True，但 zzip 和 pizzas 没有任何按顺序相同的字母，因此 match 是 False。

- Alexei Dom

---

逐个比较每个字母，并计算命中次数。最后，计算命中次数与总长度之比。然后决定。 - Haris

我认为你应该澄清“pizzaz”和“pizaz”是否应该匹配，因为如果不允许中间断开，任务会简单得多。 - Alex

difflib.get_close_matches。 - ekhumoro

你可能会发现Levenshtein距离（或其他度量标准）对于字符串相似性非常有用。 - Blender

Answer 1

你可以编写一个函数来实现这个逻辑。 zip 用于同时遍历两个字符串。

def checker(x, y):
    c = 0
    for i, j in zip(x, y):
        if i==j:
            c += 1
        else:
            break
    return c/len(x)

res = checker('pizzas', 'pizz')  # 0.6666666666666666

- jpp

Answer 2

def longestSubstringFinder(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer

ss_len = len(longestSubstringFinder("pizz", "pizzas"))
max_len = max(len("pizza"),len("pizzas"))
percent = ss_len/max_len*100
print(percent)
if(percent>=60):
    print("True");
else:
    print("False")

---

使用 动态规划 进行优化算法：

def LCSubStr(X, Y, m, n):

    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
    return result

这将直接返回LCS的长度。

- Abhishek Keshri