854. 相似度为 K 的字符串

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

示例 1：

输入：s1 = "ab", s2 = "ba"
输出：1
示例 2：

输入：s1 = "abc", s2 = "bca"
输出：2
 

提示：

1 <= s1.length <= 20
s2.length == s1.length
s1 和 s2  只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母
s2 是 s1 的一个字母异位词

先分析一下嗷，先遍历s1，判断s1[i]是否与s2[i]相等，如果相等，则判断下一个，

如果不相等，则遍历s2，直到找到一个相等的字符s2[j]，然后swap(s2[i],s2[j])，次数加一

这样写看似没问题，

但是遇到s1=abacc,s2=cbaca的情况，

最优解是只需换一次的，而上述方法需要换两次。

怎么办呢？

用递归计算所有的情况呗！反正字符串不长！

class Solution {
    int minCount = INT_MAX;
public:
    int kSimilarity(string s1, string s2) {
        dfs(s1,s2,0,0);
        return minCount;
    }
 
    void dfs(string& s1,string& s2,int cur,int index){
        if(cur>=minCount)
        return;
        if(index==s1.length()){
            minCount=min(minCount,cur);
            return;
        }
        for(int i=index;ilength();i++){
            if(s1[i]==s2[i]){
                dfs(s1,s2,cur,index+1);
            }else{
            for(int j=i+1;jlength();j++){
                    if(s1[i]==s2[j]){
                        swap(s2[i],s2[j]);
                        dfs(s1,s2,cur+1,index+1);
                        swap(s2[i],s2[j]);
                    }
                }
            }
            return;
        }
 
    }
};

这样写是没问题的，数据量很小，只用了不到300ms。

但是，并不是非得一上来就dfs的，

存在这么一种情况：

先遍历s1，判断s1[i]是否与s2[i]相等，如果相等，则判断下一个，

如果不相等，则遍历s2，直到找到一个相等的字符s2[j]，此时，再判断s2[i]与s1[j]是否相等，

如果相等，直接swap(s2[i],s2[j])，这样就是最优解，可以省去dfs的一些步骤，缩短时间。

代码如下：

class Solution {
    int minCount = INT_MAX;
public:
    int kSimilarity(string s1, string s2) {
        int ans=0;
        for(int i=0;ilength();i++)
        {
            if(s2[i]==s1[i])
            continue;
            else
            {
                for(int j=i+1;jlength();j++)
                {
                    if(s1[i]==s2[j]&&s1[j]==s2[i])
                    {
                        swap(s2[i],s2[j]);
                        ans++;
                        break;
                    }
                }
            }
        }
        dfs(s1,s2,0,0);
        return ans+minCount;
    }
 
    void dfs(string& s1,string& s2,int cur,int index){
        if(cur>=minCount)
        return;
        if(index==s1.length()){
            minCount=min(minCount,cur);
            return;
        }
        for(int i=index;ilength();i++){
            if(s1[i]==s2[i]){
                dfs(s1,s2,cur,index+1);
            }else{
            for(int j=i+1;jlength();j++){
                    if(s1[i]==s2[j]){
                        swap(s2[i],s2[j]);
                        dfs(s1,s2,cur+1,index+1);
                        swap(s2[i],s2[j]);
                    }
                }
            }
            return;
        }
 
    }
};

只用了24ms，啦啦啦