在Python中查找使两个字符串相等的最小删除次数的程序

当我们处理字符串问题时，有时需要找到使两个字符串相等的最小删除次数来使它们相等。这在字符串匹配和比较时很常见。

以下是一个Python程序，通过计算删除次数来找到使两个字符串相等的最小删除次数。

def MinimumDeletions(str1, str2):

    # 测定两字符串长度
    n1= len(str1)
    n2 = len(str2)

    # 建立动态规划矩阵    
    dp = [[0] * (n2 + 1) for i in range(n1 + 1)]

    # 填充矩阵 
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):

            # 如果末尾字符相同，则和前一个字符匹配
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]

            # 如果末尾字符不同，则删除操作要么在str1，要么在str2执行 
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 返回删除最小操作数
    return n1 + n2 - 2 * dp[n1][n2]

函数说明：这个函数采用动态规划的思想，构建了一个二维数组来记录子字符串的最长公共子序列长度，所求的解即为：字符串长度之和减去两个字符串的最长公共子序列长度的两倍。

下面是一个程序示例：

str1 = "pqrpsqp"
str2 = "pprqqrs"

result = MinimumDeletions(str1, str2)
print(result)

运行结果：

3

解释： 最小删除次数为3，第一个字符串删除 “pq” 和 “p”，第二个字符串删除 “r”。

结论

这个Python程序可以快速寻找让两个字符串相等的最小删除次数，这是一个很有用的工具，可以用于很多字符串处理任务。