Shortest word ladder

word_ladder.py

class Solution(object):

    def isAdjacent(self, first, second):

        count = 0

        for i, ch in enumerate(first):

            if first[i] != second[i]:
                count += 1

            if count >= 2:
                return False

        return True

    def solve(self, target, start, words):

        q = [(start, 0)]
        visited = {}
        found = False

        while q:
            current_word, current_length = q[0]

            for w in words:

                if w not in visited and self.isAdjacent(current_word, w) and w != current_word:
                    q.append((w, current_length + 1))
                    visited[w] = current_word

                    if w == target:
                        found = True
                        break

            if found:
                break

            q.pop(0)

        if not found:
            return []

        current = target
        path = [current]
        while current in visited:
            path.append(visited[current])
            current = visited[current]

        return list(reversed(path))


if __name__ == "__main__":
    start = "DOG"
    target = "CAT"
    words = ["DOT", "DAT", "CAT", "POT", "PAT"]
    ans = Solution().solve(target, start, words)

    print(ans)