[LeetCode][Python3] 854. K-Similar Strings

Problem :

https://leetcode.com/problems/k-similar-strings/

My Solution :

class Solution:

def kSimilarity(self, A: str, B: str) -> int:

if A == B:

return 0

checked = set([A])

queue = [A]

ans = 0

while queue:

next_queue = []

for S in queue:

S = list(S)

for i in range(len(S)):

if S[i] != B[i]:

break

for j in range(i+1, len(S)):

if S[j] == B[i] and S[j] != S[i]:

S[i], S[j] = S[j], S[i]

candidate = ''.join(S)

if candidate not in checked:

if candidate == B:

return ans + 1

checked.add(candidate)

next_queue.append(candidate)

S[i], S[j] = S[j], S[i]

queue = next_queue

ans += 1