[Problem] Word Ladder

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.
• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• sk == endWord

Given two words, eginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

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.

Approach

Extremely similar to the problem Minimum Genetic Mutation, but requires deeper thought in avoiding TLE.

1. Instead of going through the entire wordList, we can simply use the possible mutations of each word (since there's only 26 alphabets), the time complexity would only be M * M, where M is the number of characters in the word.
2. Use wordSet instead of wordList to decrease the checking time.

Everything else is pretty much the same as a typical implicit graph problem.

Solution

from collections import deque 

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        queue = deque([(beginWord, 1)])
        visited = set()
        wordSet = set(wordList)
        if endWord not in wordSet: return 0

        while queue:
            curr, cnt = queue.popleft()
            visited.add(curr)
            for i in range(len(curr)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = curr[:i] + c + curr[i+1:]
                    if next_word == endWord:
                        return cnt + 1 
                    if next_word in wordSet and next_word not in visited:
                        visited.add(next_word)
                        queue.append((next_word, cnt + 1))
        
        return 0