854. K Similar Strings - cocoder39/coco39_LC GitHub Wiki

854. K-Similar Strings

转化成bfs最短路径问题：

• string1 is string2's neighbor if we can swap 2 chars of string2 to get string2
• to transform towards s2, we need to have meaningful swap (ie, swap string1[i], string[j] iff string1[i] != destination[i] and string1[j] != destination[j] and string1[j] == destination[i])

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        visited = set()
        queue = collections.deque()
        queue.append(s1)
        visited.add(s1)
        
        k = 0
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                if cur == s2:
                    return k
                for neighbor in self.getNeighbors(cur, s2):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            
            k += 1
        return -1
    
    def getNeighbors(self, str1: str, str2: str) -> Set[str]:
        list1, list2 = list(str1), list(str2)
        i = 0
        while i < len(list2):
            if list1[i] != list2[i]:
                break
            i += 1
        
        res = set()
        for j in range(i+1, len(list2)):
            if list1[j] != list2[j] and list1[j]  == list2[i]:
                list1[i], list1[j] = list1[j], list1[i]
                res.add(''.join(list1))
                list1[i], list1[j] = list1[j], list1[i]
        return res