题解 | #字符串距离计算#

算法思想一：暴力枚举

解题思路：

枚举所有可能的X1和X2，然后计算替换之后的答案，从所有可能的答案中选取最小值

代码展示：

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        // write code here
        // 定义最小值
        int ans = 1e9;
        // 双层循环枚举 X1和X2
        for (char c = 'a'; c <= 'z'; c++) {
            for (char d = 'a'; d <= 'z'; d++) {
                int dist = 0;
                // 在计算替换之后的答案
                for (int i = 0; i < S1.size(); i++) {
                    char cur = S1[i] == c ? d : S1[i];
                    dist += (cur != S2[i]);
                }
                // 选择最小值
                ans = min(ans, dist);
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度 $O(N)$ ：N表示字符串的长度，双层枚举遍历 $O(26*26)$ 可为 $O(1)$ ，还有一层替换计算距离时间 $O(N)$

空间复杂度 $O(1)$ ：仅使用常数级变量空间

算法思想二：矩阵替换

解题思路：

1、构造一个26*26零矩阵，将a-z对应为0-25的数字

2、循环将两个字符串转换为一个矩阵的形式，同时计算两个字符串之间原始的距离

3、再枚举替换的x1,x2，寻找最大的替换字符（变换字母最多能减少的距离）

4、使用原始距离减去最大可替换的字符距离，即为替换后字符之间最小距离

注意，在变换的时候，也将对应相同字母变成了不同字母，不要忽略

图解：

代码展示：

Python版本

class Solution:
    def GetMinDistance(self , S1 , S2 ):
        # write code here
        dp = [[0] * 26 for i in range(26)]  # 构造一个26*26零矩阵，将a-z对应为0-25的数字
        diff = 0  # 字母不相同的个数，即距离
        num = 0  # 变换字母最多能减少的距离
        for i in range(len(S1)):
            dp[ord(S1[i]) - ord('a')][ord(S2[i]) - ord('a')] += 1
            # ord将字母变为ASCII码对应的数字， 将两个字符串变为一个矩阵表示
            diff += (S1[i] != S2[i])
        # 遍历替换
        for i in range(26):
            for j in range(26):
                num = max(num, dp[i][j] - dp[i][i])  # 注意，在变换的时候，也将对应相同字母变成了不同字母，不要忽略
        return diff - num

复杂度分析

时间复杂度 $O(N)$ ：N表示字符串的长度，双层枚举遍历 $O(26*26)$ 可为 $O(1)$ ，字符串遍历时间 $O(N)$

空间复杂度 $O(1)$ ：辅助矩阵占用空间 $O(26*26)$ ,因为是常数则为 $O(1)$