1.题目基本信息
1.1.题目描述
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
1.2.题目地址
https://leetcode.cn/problems/k-similar-strings/description/
2.解题方法
2.1.解题思路
广度优先搜索
- 遍历s2，比较s2[i]和s1[i]，如果相等，则跳到下一位，反之，则从s1[i+1:]中找到和s2[i]相等的元素，和s1[i]进行交换，并依次搜索所有的状态，找到最小的交换次数
A*启发式搜索
深度优先搜索
2.2.解题步骤
深度优先搜索方法步骤：
第一步，预处理。构建s和t数组，分别存储s1和s2中不匹配的字符
第二步，构建深搜递归函数。递归任务：在指针指向i，且已经花费cost的代价（交换次数）使s[:i]和t[:i]相同的情况下；继续往后进行搜索，直到i为n；且在搜索的过程中维护s==t时的最小cost
2.1.跳过s和t匹配的区域。此步必须先行，否则会报错，因为如果碰到相等元素，将导致错误的替换，造成结果被污染
2.2.递归出口
2.3.剪枝。如果不匹配的字符数为m，则至少需要交换(m+1)//2次（m在奇偶条件下都成立），所以如果预测的最小转换次数minSwapCnt+当前cost>=result，则无需继续搜索
2.4.枚举s[i+1:]部分，进一步搜索，注意调用递归后恢复s的状态
第三步，调用递归，返回结果
广度优先搜索方法步骤：
第一步，构建维护变量。que维护广搜队列，元素项的模式为(s1状态,当前比较的指针位置)；visited维护已经搜索过的s1字符串状态；steps维护广搜的层数；result维护相似度k的最小值
第二步，广度优先搜索
2.1.弹出队首节点；并将当前的s1状态与s2进行比较，观察是否可以退出
2.2.跳过当前s1状态s与s2相同的字符
2.3.枚举s的下一个状态，压入到队列中，并更新维护变量
A*启发式搜索方法步骤：
第一步，构建计算s1状态s到s2的预估距离的函数getEstimateDist，这里通过两状态之间的至小交换次数进行表示
第二步，构建获取s1的下一个状态的函数getNeigh，返回下一个状态的s1字符串列表
第三步，构建维护变量。heap维护最小堆，堆中元素项的模式为(实际距离+预估距离,当前s1字符串的状态,当前遍历到的指针位置)；distances各个结点从原始的s1到当前各个s1状态的交换次数；prePaths维护最短变化路径，各个s1状态的前驱状态
第四步，搜索
4.1.从堆中弹出"实际距离+预估距离"最小的节点；并将当前的s1状态s与s2进行比较，观察是否可以进行退出
4.2.枚举s的下一个状态，将没有搜索到或者距离更近状态压入堆中，并更新维护变量
第五步，最终distances[s2]即为s1到s2的最短距离
3.解题代码
深度优先搜索方法代码
from collections import deque
from heapq import heappop, heappush
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
# 思路3：深度优先搜索+剪枝
# 第一步，预处理。构建s和t数组，分别存储s1和s2中不匹配的字符
s, t, n = [], [], 0
for i in range(len(s1)):
if s1[i] != s2[i]:
s.append(s1[i])
t.append(s2[i])
n += 1
if n == 0:
return 0
# 第二步，构建深搜递归函数。递归任务：在指针指向i，且已经花费cost的代价（交换次数）使s[:i]和t[:i]相同的情况下；继续往后进行搜索，直到i为n；且在搜索的过程中维护s==t时的最小cost
self.result = n - 1
def dfs(i:int, cost:int) -> None:
# 2.1.跳过s和t匹配的区域。此步必须先行，否则会报错，因为如果碰到相等元素，将导致错误的替换，造成结果被污染
while i < n and s[i] == t[i]:
i += 1
# 2.2.递归出口
if i == n:
self.result = min(self.result, cost)
return
if cost > self.result:
return
# 2.3.剪枝。如果不匹配的字符数为m，则至少需要交换(m+1)//2次（m在奇偶条件下都成立），所以如果预测的最小转换次数minSwapCnt+当前cost>=result，则无需继续搜索
minSwapCnt = (sum(s[a] != t[a] for a in range(i, n)) + 1) // 2
if minSwapCnt + cost >= self.result:
return
# 2.4.枚举s[i+1:]部分，进一步搜索，注意调用递归后恢复s的状态
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 self.result
广度优先搜索方法代码
from collections import deque
from heapq import heappop, heappush
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
# 思路1：广度优先搜索。遍历s2，比较s2[i]和s1[i]，如果相等，则跳到下一位，反之，则从s1[i+1:]中找到和s2[i]相等的元素，和s1[i]进行交换，并依次搜索所有的状态，找到最小的交换次数
n = len(s1)
# 第一步，构建维护变量。que维护广搜队列，元素项的模式为(s1状态,当前比较的指针位置)；visited维护已经搜索过的s1字符串状态；steps维护广搜的层数；result维护相似度k的最小值
que = deque([(s1, 0)])
visited = set([s1])
steps = 0
result = inf
# 第二步，广度优先搜索
while que:
for _ in range(len(que)):
# 2.1.弹出队首节点；并将当前的s1状态与s2进行比较，观察是否可以退出
s, i = que.popleft()
if s == s2:
return steps
# 2.2.跳过当前s1状态s与s2相同的字符
while i < n and s[i] == s2[i]:
i += 1
# 2.3.枚举s的下一个状态，压入到队列中，并更新维护变量
for j in range(i, n):
if s2[i] == s[j]:
arr = list(s)
arr[i], arr[j] = arr[j], arr[i]
nextS = "".join(arr)
if nextS not in visited:
que.append((nextS, i + 1))
visited.add(nextS)
steps += 1
A＊启发式搜索方法代码
from collections import deque
from heapq import heappop, heappush
class Solution:
def kSimilarity(self, s1: str, s2: str) -> int:
# 思路2：A*启发式算法
n = len(s1)
# 第一步，构建计算s1状态s到s2的预估距离的函数getEstimateDist，这里通过两状态之间的至小交换次数进行表示
def getEstimateDist(s:str) -> int:
cnt = 0
for i in range(len(s2)):
if s2[i] != s[i]:
cnt += 1
return cnt // 2 + 1
# 第二步，构建获取s1的下一个状态的函数getNeigh，返回下一个状态的s1字符串列表
def getNeigh(node):
dist, s, i = node
while s[i] == s2[i]:
i += 1
arr = list(s)
ans = []
j = i
while j < n:
if s[j] == s2[i]:
arr[i], arr[j] = arr[j], arr[i]
nextS = "".join(arr)
ans.append(nextS)
arr[i], arr[j] = arr[j], arr[i]
j += 1
return ans
# 第三步，构建维护变量。heap维护最小堆，堆中元素项的模式为(实际距离+预估距离,当前s1字符串的状态,当前遍历到的指针位置)；distances各个结点从原始的s1到当前各个s1状态的交换次数；prePaths维护最短变化路径，各个s1状态的前驱状态
heap = [(getEstimateDist(s1), s1, 0)]
distances = {s1: 0}
prePaths = {s1: None}
# 第四步，搜索
while heap:
# 4.1.从堆中弹出"实际距离+预估距离"最小的节点；并将当前的s1状态s与s2进行比较，观察是否可以进行退出
addedDist, s, i = heappop(heap)
if s == s2:
return distances[s2]
# 4.2.枚举s的下一个状态，将没有搜索到或者距离更近状态压入堆中，并更新维护变量
for s3 in getNeigh((addedDist, s, i)):
newDist = distances[s] + 1
if s3 not in distances or distances[s3] > newDist:
distances[s3] = newDist
prePaths[s3] = s
heappush(heap, (newDist + getEstimateDist(s3), s3, i + 1))
# 第五步，最终distances[s2]即为s1到s2的最短距离
return distances[s2]
4.执行结果
