854. 相似度为 K 的字符串(每日一难phase2--day20)

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为基准，变换s2让两者相同
• s2中对应字符如果和s1中不同，就需要s2与后边与s1当前字符相同的字符交换
• 对应字符可能有很多，通过dfs将所有字符找出即可
• 例如：s1 = “abcbade”,s2=“caabbde”;
• a ,c不同在s2中找出所有可以交换的a交换，将所有可能遍历。
• 剪枝看具体代码

class Solution {
public:

    int res=INT_MAX;
	// 交换s2中两个字符
    void swap(string& s,int i,int j){
        char t=s[i];
        s[i]=s[j];
        s[j]=t;
    }
    // 对比每个字符找出最小值
    void dfs(string& s1,string& s2,int start,int cur ){
        // 剪枝
        if(cur>=res) return;
        // 最后一个字符不用判断，肯定相同
        if(start==s1.size()-1){
            res=min(res,cur);
            return;
        }
        // 如果当前字符不同
        if(s2[start]!=s1[start]){
            for(int j=start+1;j<s1.size();j++){
                if(s1[start]==s2[j]){
                    swap(s2,start, j); // 交换
                    dfs(s1,s2,start + 1, cur + 1);
                    swap(s2,start, j);                 }
            } 
        }else 
            dfs(s1,s2,start + 1, cur); // 当前字符相同
    }
    int kSimilarity(string s1, string s2) {
        dfs(s1,s2,0,0);
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36