字符串距离计算（840479）题解

暴力解法：
枚举所有可能的X1和X2，然后计算替换之后的答案，从所有可能的答案中选取最小值
复杂度O(26 * 26 * N)

        /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        int ans = 1e9;
        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;
    }

正解：
对于所有可能的X1, X2, 记录cnt[X1][X2]有多少个位置i, 使得S1[i] == X1, S2[i] == X2
这一步只需扫描一遍字符串即可计算得到
然后枚举可能的X1, X2，这时距离 = 原本的距离 + cnt[X1][X1] - cnt[X1][X2]
时间复杂度O(N)

        /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        int cnt[26][26];
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                cnt[i][j] = 0;
            }
        }
        int n = S1.size();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int a = S1[i] - 'a', b = S2[i] - 'a';
            cnt[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 + cnt[i][i] - cnt[i][j]);
            }
        }
        return ans;
    }