2个字符串之间的删除距离

我无法弄清楚这个问题的算法。我将粘贴问题描述以及我如何解决它，尽管这不是正确的解决方案。 它类似于编辑距离算法，我使用了相同的方法，但是有些东西不对劲，我无法弄清楚到底是什么

两个字符串之间的删除距离是ASCII码之和最小 两个字符串中需要删除的字符值 为了具有相同的字符串。 cat 和 之间的删除距离 at 是 99，因为你可以删除 cat 的第一个字符，然后 'c' 的 ASCII 值为 99。 cat 和 之间的删除距离 bat 是 98 + 99，因为你需要删除两者的第一个字符 字。当然，两个字符串之间的删除距离不能是 大于它们总 ASCII 值的总和，因为您可以 总是完全删除两个字符串。实施一个 查找两个之间的删除距离的有效函数 strings.您可以参考维基百科关于算法的文章 如果需要，可以编辑距离。那里的算法不完全是 与这里所需的算法相同，但相似。

这是我的代码。我使用了动态规划方法。 我想说最后一个“else”之后的行需要更改，但请随时纠正任何错误

def delete_distance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
    return m[len(s1)][len(s2)]

我知道这是错误的，因为delete_distance('cat', 'cbat') 的输出是197，而正确的结果应该是98，因为我们只需要删除ASCII值为98的b。

正如 Ken Y-N 之前的回答中提到的，else 部分应该至少为 3 个操作成本。 这个答案的唯一变化是 - 它被重新表述以适应您的问题。

这 3 个操作是：

• S1删除
• S2删除
• S1和S2都删除

我想以下应该有效：

def delete_distance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

希望能帮助到你！