## 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. 1 <= A.length == B.length <= 20
2. A and B 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()
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: