[LeetCode]K-Similar Strings

题目描述:

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

题目大意:

给定字符串的两个“变位词”(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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论