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