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

思路：

题目的主要信息：

• 两个长度相等的字符串距离定义为相同位置不同字符的数目
• 现有两个字符串S1与S2，从S1中任选一个字符X1，将其全部替换成另一个字符串X2后再与S2比较距离，求这个距离可能的最小值
• 两个字符串长度一定相等，全是小写字母，无特殊情况

方法一：暴力法
具体做法：
既然全是小写字母，我们替换的X1与X2也都是小写字母，因此我们可以暴力枚举所有的小写字母作为被替换和替换的情况，分别计算这个时候的距离，维护一个最小值即可。

class Solution {
public:
    int GetMinDistance(string S1, string S2) {
        int res = INT_MAX;
        for(char c1 = 'a'; c1 <= 'z'; c1++){  //枚举所有情况的X1 X2
            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++; //距离增加
                }
                res = min(res, temp); ///取最小值
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，外两层循环是遍历小写字母，内循环才是遍历字符串，计算距离
• 空间复杂度：，只有临时变量，无额外空间

方法二：矩阵替换
具体做法：
方法一中，是每次循环的时候去替换，然后计算距离，因为嵌套循环计算距离重复了很多，因此我们可以直接先计算字符串的初始距离，然后用一个的矩阵表示对于各个字母，替换之后相同的字符数，扫描一遍矩阵，找到替换之后减少最多的即可。
图中矩阵只从a-f,因为后面都没有包含了。

class Solution {
public:
    int GetMinDistance(string S1, string S2) {
        int res = INT_MAX;
        vector<vector<int> > dp(26, vector<int>(26, 0)); 
        int temp = 0;
        for(int i = 0; i < S1.length(); i++){
            dp[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++){ //遍历矩阵，找到最小距离
                res = min(res, temp + dp[i][i] - dp[i][j]); //替换之后减少的距离
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，方法一的内循环与外循环分割成了两个单独的而不是嵌套
• 空间复杂度：，辅助数组dp