【广度优先搜索】854. 相似度为 K 的字符串-技术圈

【广度优先搜索】854. 相似度为 K 的字符串

如果可以通过将 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] + 1                    queue.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为时间复杂度。

运行结果