Warning: This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#127) before relying on it.

Word Ladder

An interactive visualization of BFS on a word graph. Watch how breadth-first search explores words level by level to find the shortest transformation sequence from beginWord to endWord.

BFS LeetCode 127 ↗ Hard

The 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.

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

Interactive Visualization

Begin Word

End Word

Word List (comma-separated)

Preset

Speed:

Word Graph

BFS Queue

Queue is empty

Code

fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {    val wordSet = wordList.toMutableSet()    if (endWord !in wordSet) {        return 0    }    val queue = ArrayDeque<Pair<String, Int>>()    queue.add(beginWord to 1)    val visited = mutableSetOf(beginWord)    while (queue.isNotEmpty()) {        val (word, length) = queue.removeFirst()        for (i in word.indices) {            for (c in 'a'..'z') {                val nextWord = word.substring(0, i) + c + word.substring(i + 1)                if (nextWord == endWord) {                    return length + 1                }                if (nextWord in wordSet && nextWord !in visited) {                    visited.add(nextWord)                    queue.add(nextWord to length + 1)                }            }        }    }    return 0}

def ladderLength(beginWord, endWord, wordList):    wordSet = set(wordList)    if endWord not in wordSet:        return 0    queue = deque([(beginWord, 1)])    visited = {beginWord}    while queue:        word, length = queue.popleft()        for i in range(len(word)):            for c in 'abcdefghijklmnopqrstuvwxyz':                next_word = word[:i] + c + word[i+1:]                if next_word == endWord:                    return length + 1                if next_word in wordSet and next_word not in visited:                    visited.add(next_word)                    queue.append((next_word, length + 1))    return 0

Current Step

Press Step or Play to begin.

How It Works

Key Insight

Model the problem as a graph: each word is a node, and two words are connected by an edge if they differ by exactly one letter. Finding the shortest transformation sequence is then equivalent to finding the shortest path in an unweighted graph -- which is exactly what BFS guarantees.

The Algorithm

Build a word set from wordList for O(1) membership checks. If endWord is not in the set, return 0 immediately.
Initialize BFS with (beginWord, 1) in the queue. Mark beginWord as visited.
For each word dequeued, try changing every character position to every letter a-z:
-- If the new word equals endWord, return length + 1.
-- If the new word is in wordSet and not yet visited, mark it visited and enqueue it with length + 1.
If the queue empties without finding endWord, return 0 (no path).

Why BFS?

BFS explores all words at distance d before any word at distance d+1. The first time we reach endWord, we are guaranteed it is via the shortest path. DFS would find a path but not necessarily the shortest.

Complexity

Time O(M² x N)

Space O(M x N)

Where M is the length of each word and N is the total number of words. For each word we try 26 characters at each of M positions, and string operations take O(M). Space is dominated by the visited set and queue, each holding up to N words of length M.