Problem statement

https://binarysearch.com/problems/Dictionary-Nomad/

Solution

Equal to Leetcode 0127. Word Ladder, but here we need to use a bit more optimized approach to get AC.

Complexity

It is O(26nm^2) for time and O(26mn) for space.

Code

class Solution:
    def solve(self, wordList, beginWord, endWord):
        wordList = set(wordList)
        queue = deque([[1, beginWord]])
        while queue:
            dist, word = queue.popleft()
            if word == endWord:
                return dist
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    word1 = word[:i] + c + word[i+1:]
                    if word1 in wordList:
                        wordList.remove(word1)
                        queue.append([dist + 1, word1])
        
        return -1