题目
对于某些非负整数 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 的一个字母异位词
思路
1、自己想的是无剪枝和去重的暴力DFS和BFS搜索，但是结果都超时了
2、参考了官方题解，找到了对BFS剪枝和去重的内容
去重：用哈希表记录每次计算时得到的中间状态，当通过交换时发现当前状态已经计算过，则此时我们可以直接跳过该状态。
剪枝：我们只考虑s1[j] = s2[i] != s2[j]的情况，因为第i位后面如果第j位s1和s2已经相等，我们再做替换是多余的操作。
题解
暴力DFS超时代码
class Solution: def kSimilarity(self, A, B): ans = [] s1 = list(A) def process(s1,index,s): if ''.join(s1) == B: ans.append(s) return for i in range(index, len(s1)): for j in range(i+1, len(s1)): s1[i],s1[j] = s1[j], s1[i] process(s1, i+1, s+1) s1[i],s1[j] = s1[j], s1[i] process(s1, 0, 0) return min(ans)
BFS+剪枝+去重
class Solution: def kSimilarity(self, s1: str, s2: str) -> int: # 已走步长 step, n = 0, len(s1) # 列表模拟队列，哈希表去重 q, vis = [(s1, 0)], {s1} while True: tmp = q q = [] # 遍历队列 for s, i in tmp: if s == s2: return step while i < n and s[i] == s2[i]: i += 1 for j in range(i + 1, n): if s[j] == s2[i] != s2[j]: # 剪枝，只在 s[j] != s2[j] 时去交换 t = list(s) t[i], t[j] = t[j], t[i] t = ''.join(t) # 判重 if t not in vis: vis.add(t) q.append((t, i + 1)) step += 1
