题目描述:
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 <= A.length == B.length <= 20
A
andB
contain only lowercase letters from the set{'a', 'b', 'c', 'd', 'e', 'f'}
题目大意:
给定字符串的两个“变位词”(anagram)A和B,求最少调换多少次字符次序可以从A得到B。
解题思路:
记忆化搜索(Memoization)
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
本文链接:http://bookshadow.com/weblog/2018/06/17/leetcode-k-similar-strings/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。