【廣度優(yōu)先搜索】854. 相似度為 K 的字符串

【廣度優(yōu)先搜索】854. 相似度為 K 的字符串

如果可以通過將 A 中的兩個小寫字母精確地交換位置 K 次得到與 B 相等的字符串，我們稱字符串 A 和 B 的相似度為 K（K 為非負整數(shù)）。

給定兩個字母異位詞 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 拆分為環(huán)并進行截斷操作時，我們可以每次截斷從左到右第一個 A[i] != B[i] 對應的那條邊。即在字符串 A 和 B 中，我們每次找到最左側滿足 A[i] != B[i] 的 i，并搜索滿足 j > i 且 A[j] == B[i] 的 j。

通過這種做法，我們可以使用廣度優(yōu)先搜索遍歷所有的狀態(tài)?？梢源笾鹿烙嫵觯瑺顟B(tài)的數(shù)量為

?，如果考慮重復的字符，還需要將狀態(tài)數(shù)除以

，其中 N_i 表示 A[i] 在整個字符串中出現(xiàn)的次數(shù)。當 N \leq 20N≤20 時，狀態(tài)數(shù)量可以進行廣度優(yōu)先搜索。

代碼展示

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 相鄰 的 字符串數(shù)字    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 是字母的數(shù)量。

• 空間復雜度：O(N * t)，其中 tt為時間復雜度。

運行結果