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

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

方法一：暴力解法
$x1$ 可以是 $'a'-'z',x2$ 也可以是 $'a'-'z'$ ，所以直接枚举 $x1$ 和 $x2$ ，遍历 $S1$ ，先替换 $x1$ 为 $x2$ ,再判断 $S1[i]$ 与 $S2[i]$ 是否相等，不相等则 $dist++$ ,否则 $dist$ 不变,每一轮对 $S1$ 替换完后更新min

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    public int GetMinDistance (String S1, String S2) {
        // write code here
        //S1的
        int ans=(int)Math.pow(10,5);
        //枚举x1,x2
        for(char x1='a';x1<'z';x1++){
            for(char x2='a';x2<'z';x2++){
                int dist=0;
                for(int i=0;i<S1.length();i++){
                   char cur= S1.charAt(i)==x1?x2:S1.charAt(i);//将x1换为x2或者它本身不变
                   dist=cur!=S2.charAt(i)?dist+1:dist;//S1第i个位置的字符与S2第i个位置的字符不相同时距离+1，否则不变
                }
                ans=Math.min(ans,dist);//取最小值
            }
        }return ans;
    }
}

复杂度：
时间复杂度：第一层循环26次，第二层循环26次，第三层循环n次(n为S1的长度),则空间复杂度为 $O(26 * 26 * n)$ ;
空间复杂度：没有使用额外的存储空间，空间复杂度为 $O(1)$
方法二：
方法一是在枚举的过程中替换，需要三重循环，优化后的方法是先计算 $x1$ 未替换为 $x2$ 时的距离，通过cnt二维数组存储所有替换方法的减少距离数，具体方法是对 $cnt[x1-'a'][x2-'a']$ 进行统计，如果S1中有n个 $x1$ ,S2对应位置有n个 $x2$ ,则n个 $x1$ 都可以被替换为相同的 $x2$ ,所以 $cnt[x1-'a'][x2-'a']$ 累计n次，表示这一种替换方法可以减少的距离数为n,每种替换方法下的最终距离 $=dist+cnt[i,i]-cnt[i,j]$ （当 $x1,x2$ 不相等时， $cnt[i][i]$ 为0,则相当于减去 $cnt[i][j]$ ,如果 $x1,x2$ 相等，则原本不相等的位置已经被统计为 $dist$ , $cnt[i][i]=cnt[i][j]$ ，则减去0, $dist$ 不变）
最后，再遍历cnt数组，求得距离最小值
图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    public int GetMinDistance (String S1, String S2) {
        // write code here
        //S1的
        int[][]cnt=new int[26][26];
        int dist=0;
        for(int i=0;i<S1.length();i++){
            char x1=S1.charAt(i);
            char x2=S2.charAt(i);
            cnt[x1-'a'][x2-'a']++;//假如S1有n个x1,S2对应位置有n个x2,则n个x1都可以被替换为相同的x2所以cnt[x1-'a'][x2-'a']会累加到n
            if(x1!=x2)
                dist++;//记录x1未替换为x2时的距离
        }
        int res=Integer.MAX_VALUE;
        //枚举x1,x2的可能情况
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                //遍历矩阵，找到距离的最小值
                res=Math.min(res,dist+cnt[i][i]-cnt[i][j]);//替换后减少的距离
            }
        }
        return res;
    }
}

复杂度：
时间复杂度：需要遍历一次字符串，时间复杂度为 $O(n)$ (n为字符串的长度)
空间复杂度：额外使用的cnt数组大小为26*26,常数级空间，所以空间复杂度为 $O(1)$