【广度优先搜索】854. 相似度为 K 的字符串
DayNightStudy
共 1191字，需浏览 3分钟
·
2021-01-30 23:10
如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串，我们称字符串 A 和 B 的相似度为 K（K 为非负整数）。
给定两个字母异位词 A 和 B ，返回 A 和 B 的相似度 K 的最小值。
示例 1：
输入：A = "ab", B = "ba"
输出：1
示例 2：
输入：A = "abc", B = "bca"
输出：2
示例 3：
输入：A = "abac", B = "baca"
输出：2
示例 4：
输入：A = "aabc", B = "abca"
输出：2
提示：
1 <= A.length == B.length <= 20
A 和 B 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母。
题目解析
题目解答
当我们把基础图 G 拆分为环并进行截断操作时，我们可以每次截断从左到右第一个 A[i] != B[i] 对应的那条边。即在字符串 A 和 B 中，我们每次找到最左侧满足 A[i] != B[i] 的 i，并搜索满足 j > i 且 A[j] == B[i] 的 j。
通过这种做法，我们可以使用广度优先搜索遍历所有的状态。可以大致估计出，状态的数量为
，如果考虑重复的字符，还需要将状态数除以
，其中 N_i 表示 A[i] 在整个字符串中出现的次数。当 N \leq 20N≤20 时，状态数量可以进行广度优先搜索。
代码展示
class Solution:def kSimilarity(self, A: str, B: str) -> int:queue = collections.deque([A])seen = {A: 0}while queue:S = queue.popleft()if S == B:return seen[S]for T in self.neighbors(S,B):if T not in seen:seen[T] = seen[S] + 1queue.append(T)# 功能：获取 所有 与 B 相邻 的 字符串数字def neighbors(self,S,B):# step 1：找到 第一个 与 B 对应位置不同的 位置for i, c in enumerate(S):if c != B[i]:break# step 2：在 [i+1, len(S)] 中找到与B[i]相同的元素交换T = list(S)for j in range(i+1, len(S)):if S[j] == B[i]:T[i], T[j] = T[j], T[i]yield "".join(T)T[j], T[i] = T[i], T[j]
复杂度计算
时间复杂度：
其中 N 是字符串的长度，W 是字母的数量。
空间复杂度：O(N * t)，其中 tt为时间复杂度。
运行结果
评论