LeetCode 127 Word Ladder - Implementation - Breadth First Search (BFS) | Graph Theory

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

Word Ladder asks you to transform one word into another by changing one letter at a time. Each intermediate word must exist in the dictionary. BFS finds the shortest transformation sequence.

Here's the solution:

function ladderLength(beginWord, endWord, wordList):
    wordSet := set of all words in wordList
    if endWord not in wordSet:
        return 0

    queue := empty queue
    push (beginWord, 1) to queue
    visited := set containing beginWord

    while queue is not empty:
        (word, steps) := pop from queue

        for i from 0 to length(word) - 1:
            for c from 'a' to 'z':
                newWord := word with character at i replaced by c

                if newWord = endWord:
                    return steps + 1

                if newWord in wordSet and newWord not in visited:
                    add newWord to visited
                    push (newWord, steps + 1) to queue

    return 0

For each word, you try all $26$ letters at each position. If the new word exists in your word set and you haven't visited it, add it to the queue. The first time you reach endWord, you've found the shortest path.

Time: $O(N \times L \times 26)$ where $N$ is the word count and $L$ is word length. Space: $O(N)$ for the queue and visited set.