Word Ladder (BFS on an implicit graph).

Problem. Given beginWord, endWord, and a wordList, find the length of the shortest transformation sequence from beginWord to endWord where each step changes exactly one letter and every intermediate word is in the list. Return 0 if no sequence exists. Length counts the words in the path (so hit → hot → dot → dog → cog has length 5).

Why BFS — it's shortest path on an implicit graph

Each word is a vertex; two words are adjacent iff they differ by one letter. Every edge has weight 1, so the shortest transformation = fewest edges = BFS. The graph is implicit: you never materialize it, you generate neighbors on demand.

Generating neighbors efficiently

The naive neighbor check compares every pair of words — O(N²·L). Better: for a word of length L, try all 26·L one-letter mutations and keep those present in a HashSet of the word list. That's O(26·L) per word, independent of list size, and the set membership check is O(L) for hashing.

Approach — BFS, O(N · L²) time, O(N · L) space

int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return 0;          // target unreachable

    Queue<String> q = new ArrayDeque<>();
    q.add(beginWord);
    Set<String> visited = new HashSet<>();
    visited.add(beginWord);

    for (int level = 1; !q.isEmpty(); level++) {
        for (int i = q.size(); i > 0; i--) {        // drain one BFS level
            String word = q.poll();
            if (word.equals(endWord)) return level;
            char[] chars = word.toCharArray();
            for (int p = 0; p < chars.length; p++) {
                char original = chars[p];
                for (char c = 'a'; c <= 'z'; c++) {  // 26 mutations at position p
                    if (c == original) continue;
                    chars[p] = c;
                    String next = new String(chars);
                    if (dict.contains(next) && visited.add(next))
                        q.add(next);                 // mark on enqueue
                }
                chars[p] = original;                 // restore for next position
            }
        }
    }
    return 0;
}

With N words of length L, each word generates 26·L candidates and building each string is O(L), giving O(N · L²) time. visited.add returning false skips re-enqueues, so each word is processed once.