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

#include <algorithm>
#include <cassert>
#include <memory>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        assert(S1.size() == S2.size());
        // 小写字母数量比较少，因此直接遍历26*26空间，少遍历整个字符串
        vector<vector<int>> mat(26, vector<int>(26,
                                                0)); //保存把某个字母换成某个字母的距离
        for (int i = 0; i < S1.size(); i++) { //尽量只遍历一次字符串
            for (int j = 0; j < 26; j++) {
                for (int k = 0; k < 26; k++) {
                    mat[j][k]++;
                    if (S1[i] - 'a' == j && S2[i] - 'a' == k) {
                        mat[j][k]--;
                    }else if (S1[i]==S2[i] && S1[i] - 'a' != j) {
                        mat[j][k]--;
                    }
                }
            }
        }
        int minDist = mat[0][0];
        for (vector<int> row : mat) {
            for (int item : row) {
                minDist = min(minDist, item);
            }
        }
        return minDist;
    }
};

因为小写字母很少，直接计算所有字符串的距离。mat[j][k]表示S1'和S2的距离，其中S1'为S1中j号小写字母变为k号小写字母得到的字符串。每一轮，除非j改为k之后对应字符串相同，或者没发生交换本来相同，否则都要距离++。