Участник:Turk0v/K-Similar Strings

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution:
    def nei(self,X,B,N):
            i = 0
            while X[i] == B[i]:
                i += 1
            return [X[:i]+X[j]+X[i+1:j]+X[i]+X[j+1:] for j in range(i+1, N) if X[j] == B[i]]
 
    def kSimilarity(self, A: str, B: str) -> int:
        N = len(B)
        q, res = [(A, 0)], {A}
        for X, d in q:
            if X == B:
                return d
            for Y in self.nei(X,B,N):
                if Y not in res:
                    res.add(Y)
                    q.append((Y, d+1))