难度: Hard
对于某些非负整数 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 <= 20s2.length == s1.lengths1 和 s2 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母s2 是 s1 的一个字母异位词运行时间: 47 ms
内存: 16.1 MB
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
s, t = [], []
for x, y in zip(s1, s2):
if x != y:
s.append(x)
t.append(y)
n = len(s)
if n == 0:
return 0
ans = n - 1
def dfs(i, cost):
nonlocal ans
if cost > ans:
return
while i < n and s[i] == t[i]:
i += 1
if i == n:
ans = min(ans, cost)
return
diff = sum(s[j] != t[j] for j in range(i, len(s)))
min_swap = (diff + 1) // 2
if cost + min_swap >= ans:
return
for j in range(i + 1, n):
if s[j] == t[i]:
s[i], s[j] = s[j], s[i]
dfs(i + 1, cost + 1)
s[i], s[j] = s[j], s[i]
dfs(0, 0)
return ans
此题解采用了深度优先搜索（DFS）的方法来求解字符串s1通过最少次数的交换变为字符串s2的问题。首先，它通过一个循环去除掉s1和s2中相同位置上相同的字符，只保留不同的字符，从而减少了问题的规模。然后，定义一个递归函数dfs来尝试所有可能的字符交换，通过递归搜索找到最小的交换次数。递归过程中使用了剪枝来减少不必要的计算，例如，如果当前已有的交换次数已经超过了已知的最小交换次数，就停止进一步搜索。此外，还计算了当前不匹配的字符对至少需要的交换次数来进行更深入的剪枝。
时间复杂度: O(n!)
空间复杂度: O(n)
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
s, t = [], []
for x, y in zip(s1, s2):
if x != y: # 收集所有不同的字符对
s.append(x)
t.append(y)
n = len(s)
if n == 0: # 如果没有不同的字符，直接返回0
return 0
ans = n - 1 # 初始化最小交换次数为n-1
def dfs(i, cost):
nonlocal ans # 引用外部变量ans
if cost > ans: # 如果当前成本已经超过已知最小值，则剪枝
return
while i < n and s[i] == t[i]: # 跳过已经匹配的位置
i += 1
if i == n: # 如果所有位置都匹配了
ans = min(ans, cost)
return
diff = sum(s[j] != t[j] for j in range(i, len(s))) # 计算剩余不匹配的数量
min_swap = (diff + 1) // 2 # 估算至少还需要的交换次数
if cost + min_swap >= ans: # 使用估算值进行剪枝
return
for j in range(i + 1, n):
if s[j] == t[i]: # 查找可以与s[i]交换的字符s[j]
s[i], s[j] = s[j], s[i] # 执行交换
dfs(i + 1, cost + 1) # 递归搜索下一步
s[i], s[j] = s[j], s[i] # 撤销交换
dfs(0, 0) # 从第0位开始搜索
return ans # 返回最小交换次数
在`dfs`函数中，当`n == 0`时可以直接返回0，是因为`n`代表的是s1和s2中位置相同但字符不同的字符对的数量。如果`n`为0，这意味着没有这样的字符对，即s1和s2在所有相同位置上的字符完全相同。因此，不需要任何交换操作，s1已经和s2完全相同了。
在选择进行交换的字符时，考虑`s[j] == t[i]`的情况是因为这样的交换能直接解决位置`i`的不匹配问题，即将位置`i`的字符直接变为目标字符`t[i]`。虽然理论上可以考虑其他交换以期望通过多步骤达到整体最优，但这通常会导致问题复杂度急剧增加，并且难以保证得到最小交换次数。因此，题解中主要考虑这种可以直接减少不匹配数量的有效交换。
这种剪枝策略的逻辑是基于当前搜索路径的成本。如果在`dfs`递归过程中，当前路径上已经累积的交换次数（成本）超过了之前找到的最小交换次数，那么继续当前路径的搜索只会得到更大的交换次数。因此，可以立即停止当前路径的进一步搜索，这样做能有效减少不必要的计算，提高算法的效率。
计算公式`(diff + 1) // 2`用于估算至少还需要的交换次数，其中`diff`是当前不匹配的字符对的数量。这个公式基于一个简单的假设：每一次有效的交换至少可以解决一个字符对的不匹配。因此，在最理想的情况下，每两个不匹配的字符通过一次交换可以被修正（考虑到交换是两个字符间的操作）。所以，`diff`个不匹配的字符对至少需要`diff / 2`次交换，而`(diff + 1) // 2`是`diff / 2`向上取整的结果，确保覆盖所有奇数情况。