## 题目描述：

LeetCode 854. K-Similar Strings

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'}`

## Python代码：

``````class Solution(object):
def kSimilarity(self, A, B):
"""
:type A: str
:type B: str
:rtype: int
"""
self.memo = {}
return self.solve(A, B)

def solve(self, A, B):
diff = [A[i] != B[i] for i in range(len(A))]
simplify = lambda S: ''.join(c * d for c, d in zip(S, diff))
A, B = simplify(A), simplify(B)
if not A: return 0
if (A, B) in self.memo: return self.memo[(A, B)]
ans = 0x7FFFFFFF
for i, x in enumerate(A):
if A[i] == B[0]:
C = A[1:i] + A[0] + A[i+1:]
ans = min(ans, self.solve(C, B[1:]))
self.memo[(A, B)] = ans + 1
return ans + 1
``````

Pingbacks已关闭。