# Word Ladder Solution Guide

### Question
[Original Question](https://leetcode.com/problems/word-ladder/description/)

### Explanation of the solution
The solution treats words as nodes in a graph, with an edge between each word with only a one-letter difference between them. For example, `hot` and `hog` would have an edge between them but `hot` and `dog` would not. In this kind of graph, finding the shortest path between two words can be done with a breadth-first traversal of the graph.

We don’t need to build up this graph, as we can just check whether edges exist on the fly. For example, for the word `hot`, we can generate all neighbors by just changing each letter and checking whether the new word is in the word list.

We use a queue to keep track of the nodes in the graph we are exploring, making sure to keep track of the distance from the start node in the queue. Furthermore, we make sure to keep track of words we have already visited, so we don’t get stuck in a cycle. Finally, when the node we pop off the queue is the end word, we return the length of the ladder. If we search the whole graph without finding the end word, we return 0.

**Python Solution**

LETTERS = set('abcdefghijklmnopqrstuvwxyz')

def word_ladder(start, end, words):
    words = set(words)
    visited = set()
    queue = [(start, 1)] # queue for BFS, which stores the word and distance

    while len(queue) > 0:
        word, length = queue.pop(0)
        if word == end:
            return length
        for i, char in enumerate(word):
            for letter in LETTERS:
                if char != letter:
                    candidate = word[:i] + letter + word[i + 1:]
                    if candidate in words and candidate not in visited:
                        queue.append([candidate, length + 1])
                        visited.add(candidate)
    return 0

### Complexity Analysis

**Time complexity:** O(N * M)
* N = size of the dictionary
* M = length of the word

**Space complexity:** O(N)
* N = size of the dictionary

###### tags: `Week 5-Graphs`