一、题目
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
二、示例
2.1> 示例 1：
【输入】s1 = "ab", s2 = "ba"
【输出】1
2.2> 示例 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=“bccaba”，s2=“abacba”为例，展示一条路线的交换遍历过程，如下图所示：
通过上面的图例，我们了解到了一条路线的计算交换方式，但是，由于我们会针对每一步都会执行回溯操作（如果满足回溯条件的话），那么就会有N条路线。还是以上面的例子，如下列出了可能
路线很多，但是我们也没有必要全都执行完每条路线的遍历操作。比如，当我们遍历一条路线进行交换操作的时候，发现已经超过了其他路线的最小交换次数，那么这条路线我们就没有必要在继续走下去了。具体的逻辑处理，请参照如下的代码实现。
四、代码实现
class Solution {
int result = Integer.MAX_VALUE;
public int kSimilarity(String s1, String s2) {
return execute(s1.toCharArray(), s2.toCharArray(), 0, 0);
}
public int execute(char[] sc1, char[] sc2, int start, int current) {
if (current >= result) return result; // 如果交换次数已经超过"目前最小交换次数result"，终止递归
if (start == sc1.length - 1) return result = Math.min(current, result);
for (int i = start; i < sc1.length; i++) {
if (sc1[i] != sc2[i]) {
for (int j = i + 1; j < sc2.length; j++) {
if (sc2[j] == sc1[i] && sc2[j] != sc1[j]) {
swap(sc2, i, j); // 交换
execute(sc1, sc2, i + 1, current + 1);
swap(sc2, i, j); // 回溯
if (sc2[i] == sc1[j]) break; // 如果sc1和sc2的i位于j位互为相等，那么就是最优交换
}
}
return result;
}
}
return result = Math.min(current, result);
}
public void swap(char[] sc, int i, int j){
char temp = sc[i];
sc[i] = sc[j];
sc[j] = temp;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
