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

字符串距离计算

http://www.nowcoder.com/practice/82bd533cd9c34df29ba15bbf1591bedf

题意

两个等长的字符串A,B，现在将A中指定的一种字符全部替换，问替换后和B位置一一对应上不同的字符数量最少是多少个。

其中字符串长度小于 $5\cdot 10^4$ , 字符全为小写字母

方法

枚举替换

我们枚举所有替换对，也就是'a'-'z'替换为'a'-'z'.

再对每一种替换，做不同的字符数量的统计。每次统计更新最大值。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        int n = S1.length();
        int ans = n;
        // 枚举 把a中的所有字符 ch 换成 ch2 的所有情况
        for(char ch='a';ch<='z';ch++){
            for(char ch2='a';ch2<='z';ch2++){
                int cnt = 0;
                for(int i = 0;i<n;i++){
                    cnt += S2[i] != (S1[i] == ch?ch2:S1[i]); // 如果不同则计数+1
                }
                ans = min(ans,cnt); // 最小的不同数
            }
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 我们只有总数，和遍历使用了额外变量，所以空间复杂度为 $O (1)$

时间复杂度: 我们尝试了所有替换对，替换对数量为常数，每次对于一个具体的替换对，遍历了两个字符串，所以时间复杂度为 $O (n)$

分类统计

如果我们把字符甲换成字符乙，那么这时只会对原来和甲相关有的有影响。

总共有三种情况:

A	甲	甲	甲
B	甲	乙	非甲也非乙

那么更换后

A	乙	乙	乙
B	甲	乙	非甲也非乙

所以不同的字符数量变化为为 原来(甲,甲) - 原来(甲,乙)

注意到小写字母有26个。

我们对于相同的情况只需要26大小的空间来统计

对于不同的情况需要 $26 \cdot 26$ 大小的空间来统计有多少对。

由此，我们统计完后，检查所有统计数据，找到能让原来(甲,甲) - 原来(甲,乙)变化最大的，在加上初始的不同的个数即可

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        int dis = 0;
        map<pair<char,char>,int> ab2cnt ; // ab2cnt[ch0][ch1] = a中字符是ch0对应位置b中对应位置是ch1的数量
        map<char,int> a2cnt ; // a2cnt[ch] = a中字符ch 对应位置b中也是ch的数量
        int n = S1.length();
        for(int i = 0;i<n;i++){ // 统计上面两种信息
            if(S1[i] != S2[i]){
                dis++;
                ab2cnt[{S1[i],S2[i]}]++;
            }else{
                a2cnt[S1[i]]++;
            }
        }
        int maxcost = 0;
        for(auto item:ab2cnt){ // 尝试所有替换方案
            char ch = item.first.first;
            maxcost = max(maxcost, item.second - a2cnt[ch]); // 增量为 新增相同 减去 失去的相同的 
        }
        return dis - maxcost;
    }
};