Leetcode 127. Word Ladder

Problem

Leetcode 127 - Word Ladder

Example:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Approach

We can use BFS to find the words that have similar words in wordList. Once we find the correct word, we can return the counts that we’ve searched through

Here is the Python code for the solution:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if beginWord == endWord or endWord not in wordList:
            return 0
        
        words, res = set(wordList), 0
        q = deque([beginWord])
        while q:
            res += 1
            for _ in range(len(q)):
                node = q.popleft()
                if node == endWord:
                    return res
                for i in range(len(node)):
                    for c in range(97, 123):
                        if chr(c) == node[i]:
                            continue
                        nei = node[:i] + chr(c) + node[i+1:]
                        if nei in words:
                            q.append(nei)
                            words.remove(nei)

        return 0    

Time Complexity and Space Complexity

Time Complexity: $O(m^2 * n)$

Space Complexity: $O(m^2 * n)$