K-Similar Strings

Intuition

Solution

class Solution:
    def __init__(self):
        self.cache = {}

    def kSimilarity(self, A: str, B: str) -> int:
        if A + B in self.cache:
            return self.cache[A + B]
        if A == B:
            return 0

        for i in range(len(A)):
            if A[i] != B[i]:
                start = i
                break
        ans = len(A)
        for i in range(start + 1, len(A)):
            if B[i] == A[start] and A[i] != A[start]:
                tmp = B[:start] + B[i] + B[start + 1:i] + B[start] + B[i + 1:]
                ans = min(ans, self.kSimilarity(A, tmp) + 1)
        self.cache[A + B] = ans
        return ans