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

题目：字符串距离计算
描述：给定两个长度相等的，由小写字母组成的字符串S1和S2，定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。现在牛牛可以选定两个字母X1和X2，将S1中的所有字母X1均替换成X2。（X1和X2可以相同），牛牛希望知道执行一次替换之后，两个字符串的距离最少为多少。
示例1：输入："aaa","bbb"，返回值：0
说明：牛牛可以将S1中的字符'a'全部替换成字符'b'，这样S1就变成了"bbb"，那么S1和S2的距离就是0
示例2：输入："aabb","cdef"，返回值：3
说明：一种可行的方案是将S1中的字符'a'全部替换成字符'c'，那么S1变成了"ccbb"，和S2的距离是3

解法一：
思路分析：首先我们分析题目，题目的大意就是通过替换，使得S1与S2的近似度最高，且只能替换一次，替换完成之后，两个字符的距离最少，所谓距离就是有多少个位置上的字母不相等。
——通过分析，我们明白了题目的意思，下面我们进行计算，因为英文一共有26个字母，所以可以创建一个dp的二维数组，dp[26][26]，初始化，每一个量对应的值都为0，其次，通过设定一个指针来判断相同序号的S1与S2不相等的位数一共有多少，方便进行下一步判断，当我们知道有多少个不相等的位数后，我们就需要替换S1中的X1字符，改变为X2，如何改变呢，我们可以通过二维数组中的依次循环，使用dp[i][i] - dp[i][j]（例如当S1中有一个元素为a，S2中有一个元素为b，所以其dp[0][1] = 1，当将S1中的元素a换为b时，dp[1][1]初始化为0，0 - 1 = -1，所以就相当于抵消了一个元素，所以将不同的位数之和sum + -1，就能得到一个新的最小位数不同的量了）来判断换变量以后有多少元素变成相同的了，然后用sum加上，就可以得到最终的最小值。
实例分析：输入："aabb","cdef"，返回值：3
——初始化，我们首先创建一个dp[][]的二维数组用来存储S1与S2相同与不同序号的值，因为元素的最大范围为f，所以我们使用一个 $图片说明$ 的数组代替 $图片说明$ 的数组。

——根据上述表格，我们进行分析，初始化表格的数据都是0，S1中的第一个元素为a，S2中的第一个元素为c，所以dp[0][2]++，依次进行判断，得到一个新的表格。

——新的表格如上，只要（代码中设定的值）a与b的值不相等，就将sum的值进行累加，如果相等，就不需要进行考虑。经过循环得到sum的值为4，说明四组数据对应的均不相等，下一步，替换S1中的元素，判断可能有多少位元素不同。
图片说明
——上述红颜色的代表，S1与S2元素值相同的，当将S1中的a替换为c时，出现了如下情况。

——所以其dp[2][2] - dp[0][2] = -1（原始数据），最终得到sum最小为3，其他情况与此情况类似，就不一一进行讨论。
C++核心代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        // write code here
        int dp[26][26];//创建二维数组
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                dp[i][j] = 0;//初始化每个元素都为0
            }
        }
        int len = S1.size();//S1字符串的长度
        int sum = 0;//用来存储不相等的位数
        for (int i = 0; i < len; i++) {
            int a = S1[i] - 'a', b = S2[i] - 'a';
            dp[a][b]++;//对应的二维数组增加一个值
            sum += (a != b);//不等的位数
        }
        int ans = sum;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                ans = min(ans, sum + dp[i][i] - dp[i][j]);
                //当换变量以后，不同的位数值最小为……
            }
        }
        return ans;
    }
};

——因为刚开始创建了一个dp的二维数组，需要将其内的数组元素循环设置为0，所以其时间复杂度为 $O(N^2)$ ，接下来，需要循环判断S1的大小元素与S2的大小元素，所以这一部分的时间复杂度为 $O(M)$ ，最终时间复杂度为 $O(N^2 + M)$ ，因为存储空间为常数，所以其空间复杂度为 $O(1)$ 。
解法二：
思路分析：我们同样也可以使用暴力法进行分析，既然S1与S2中的元素均是小写字母，我们也可以使用暴力法的方式，将所有可能枚举出来，分别分析替换的情况，然后计算出各自的距离，最后使用min求出最小值返回即可。
C++核心代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        // write code here
        int res = INT_MAX;//将res初始化
        for(char i = 'a'; i <= 'z'; i++){//从a到z依次循环判断
            for(char j = 'a'; j <= 'z'; j++){
                int temp = 0;//存储距离的变量
                int len = S1.size();
                for(int k = 0; k < len; k++){
                    //循环S1中的全部字符
                    if(S1[k] == i){//如果相同
                        S1[k] = j;//替换
                        temp = S1[k] != S2[k] ? temp + 1 : temp;//将距离的值改变
                        S1[k] = i;
                    }
                    else if(S1[k] != S2[k])//不同则不需要替换，直接将距离增加即可
                        temp++;
                }
                res = min(res, temp);
            }
        }
        return res;
    }
};

——在此循环中，因为直接挨个循环26个字符，和解法一不相同的是，解法二直接进行遍历判断，所以其时间复杂度为 $O(26*26*N)$ ，其中N为S1的字符数量。因为在此暴力循环中，没有设定额外的数组去辅助存储，所以其空间复杂度为 $O(1)$ 。