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 <= 20
A
andB
contain 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)