Crack the Backend

Problem Statement

Given beginWord, endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord (the number of words in the sequence, so beginWord is 1). Each step you may change exactly one letter to get a word that is in wordList. If no such sequence exists, return 0. beginWord may or may not be in wordList.

BFS: State is the current word. Neighbors are all words in wordList that differ by exactly one letter. The first time we reach endWord we have the shortest length. We can remove a word from the set when we enqueue it (so we never visit it again with a longer path).

Key Observations

Put wordList in a Set for O(1) lookup. Queue (beginWord, 1). While queue not empty: dequeue (word, len). If word.equals(endWord) return len. For each position i and each letter 'a'-'z', form next by replacing word.charAt(i); if set.contains(next), remove next from set (so we don't revisit), enqueue (next, len+1). If queue empties, return 0.

Approach

High-level: Set = wordList. BFS from (beginWord, 1). For each (word, len): if word==endWord return len. For each index i and char c: next = word with [i]=c; if next in set, set.remove(next), enqueue (next, len+1). Return 0 if queue empties.

Implementation

Java

public int ladderLength(String begin, String end, List<String> wordList) {
    Set<String> set = new HashSet<>(wordList);

    if (!set.contains(end)) {
        return 0;
    }

    Queue<String> q = new ArrayDeque<>();
    q.offer(begin);
    set.remove(begin);
    int len = 1;

    while (!q.isEmpty()) {
        for (int size = q.size(); size > 0; size--) {
            String w = q.poll();

            if (w.equals(end)) {
                return len;
            }

            char[] arr = w.toCharArray();

            for (int i = 0; i < arr.length; i++) {
                char orig = arr[i];

                for (char c = 'a'; c <= 'z'; c++) {
                    arr[i] = c;
                    String next = new String(arr);

                    if (set.remove(next)) {
                        q.offer(next);
                    }
                }

                arr[i] = orig;
            }
        }

        len++;
    }

    return 0;
}

Test Cases

Example 1

Input

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Expected

5

Explanation

hit->hot->dot->dog->cog (5 words).

Complexity Analysis

Time: O(M^2 * N) M=word length, N=list size.
Space: O(N).

Follow-ups

Word Ladder II: return all shortest sequences.