854. 相似度为 K 的字符串
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
输入：s1 = "ab", s2 = "ba"
输出：1
- 广度优先搜索
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
# 题意为从 s1 变换为 s2，最小的变换次数 k
# 枚举所有可能的交换方案，在搜索时进行减枝从而提高搜索效率，最终找到最小的交换次数
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]:
t = list(s)
# 剪枝，只在s[j] != s2[j] 时交换
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
