字符串距离计算

[编程题]字符串距离计算

热度指数：3882 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个长度相等的，由小写字母组成的字符串S1和S2，定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。

现在牛牛可以选定两个字母X1和X2，将S1中的所有字母X1均替换成X2。（X1和X2可以相同）

牛牛希望知道执行一次替换之后，两个字符串的距离最少为多少。

示例1

输入

"aaa","bbb"

输出

说明

牛牛可以将S1中的字符'a'全部替换成字符'b'，这样S1就变成了"bbb"，那么S1和S2的距离就是0

示例2

输入

"aabb","cdef"

输出

说明

一种可行的方案是将S1中的字符'a'全部替换成字符'c'，那么S1变成了"ccbb"，和S2的距离是3

备注:



S1和S2中的字母均为小写字母

算法知识视频讲解

Python

白色高跟鞋

def cal(s1, s2):
    dp = [[0] * 26 for _ in range(26)]  # 在某个位置上，有dp[x1][x2]个s1[x1]和s2[x2]
    sums, res = 0, 0
    for i in range(len(s1)):
        dp[ord(s1[i]) - ord('a')][ord(s2[i]) - ord('a')] += 1
        sums += (s1[i] != s2[i])
    return sums - max([dp[i][j] - dp[i][i] for j in range(26) for i in range(26)])

@ see: https://blog.nowcoder.net/n/6e99cd8fabb248d1920ce6931e8fb861

编辑于 2020-05-16 11:56:55 回复(0)