Description
Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.
Given two anagrams A and B, return the smallest K for which A and B are K-similar.
Example 1:
Input: A = "ab", B = "ba"
Output: 1
Example 2:
Input: A = "abc", B = "bca"
Output: 2
Example 3:
Input: A = "abac", B = "baca"
Output: 2
Example 4:
Input: A = "aabc", B = "abca"
Output: 2
Note:
1 <= A.length == B.length <= 20AandBcontain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}
Solutions
找到从 A 每次交换两个字母变换到 B 所用的最少交换次数。
1. BFS
其实这就是搜索的题目，而且是要找到最短的，可以通过 BFS 的分支限界法求解。
# Time: O(?)
# Space: O(n)
class Solution:
def kSimilarity(self, A: str, B: str) -> int:
res, n = 0, len(A)
visited = set()
visited.add(A)
queue = collections.deque()
queue.append(A)
while queue:
size = len(queue)
for _ in range(size):
T = queue.popleft()
if T == B:
return res
i = 0
while i < n and T[i] == B[i]:
i += 1
T = list(T)
for j in range(i+1, n):
if T[j] == B[j] or T[j] != B[i]:
continue
T[i], T[j] = T[j], T[i]
if ''.join(T) not in visited:
visited.add(''.join(T))
queue.append(''.join(T))
T[i], T[j] = T[j], T[i]
res += 1
return -1
# 54/54 cases passed (184 ms)
# Your runtime beats 60.39 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (14 MB)