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

题目描述
给定两个长度相等的，由小写字母组成的字符串S1和S2，定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。
现在牛牛可以选定两个字母X1和X2，将S1中的所有字母X1均替换成X2。（X1和X2可以相同）
牛牛希望知道执行一次替换之后，两个字符串的距离最少为多少。

方法一：暴力方法

求解思路
对于本题目，给出的条件中，因为全是小写字母，我们替换的X1和X2也都是小写字母，因此我们可以暴力枚举所有的小写字母作为被替换和替换的情况，然后分别计算每种情况的距离，然后从中求出最小值即可。

图片说明

解题代码

class Solution {
public:
    int GetMinDistance(string S1, string S2) {
        int myres = INT_MAX;
        for(char c1 = 'a'; c1 <= 'z'; c1++)
        {
            for(char c2 = 'a'; c2 <= 'z'; c2++)
            {
                int temp = 0; // 声明临时变量
                for(int i = 0; i < S1.length(); i++)
                {
                    if(S1[i] == c1) // 计算距离
                    {
                        S1[i] = c2;
                        temp = S1[i] != S2[i] ? temp + 1 : temp; // 增加距离
                        S1[i] = c1;
                    }
                    else if(S1[i] != S2[i]) // 没有替换
                        temp++; // 距离增加
                }
                myres = min(myres, temp); // 取最小值
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：外层为常数级循环，内层为一层循环，因此时间复杂度为 $O(N)$
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$

方法二：优化方法--矩阵替换

求解思路
对于方法一，每次循环替换字母，然后计算距离。我们对其进行优化，首先我们计算字符串的初始距离，然后用一个26*26的矩阵表示各个字母，替换之后相同的字符数，扫描一遍矩阵后，找到替换以后的减少最多的字符，最后即可得到本题的答案。

图片说明

解题代码

class Solution {
public:
    int GetMinDistance(string S1, string S2) {
        int myres = INT_MAX; // 声明结果
        vector<vector<int> > mydp(26, vector<int>(26, 0)); 
        int temp = 0; // 声明临时变量
        for(int i = 0; i < S1.length(); i++)
        {
            mydp[S1[i]- 'a'][S2[i] - 'a']++; 
            if(S1[i] !=S2[i]) // 记录初始距离
                temp++; // 更新临时变量
        }
        for(int i = 0; i < 26; i++)
        {
            for(int j = 0; j < 26; j++)
            {   //遍历矩阵，找到最小距离
                myres = min(myres, temp + mydp[i][i] - mydp[i][j]); // 替换之后减少的距离
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：辅助数组dp[26][26]，常数级内存空间，因此空间复杂度为 $O(1)$