Word Ladder

The problem, simply

You get a start word, an end word, and a list of allowed words, all the same length. In one step you may change exactly one letter, and the new word must be in the list. The start word does not need to be in the list.

Give back the number of words in the shortest ladder from the start word to the end word, counting both ends. If there is no ladder, give back 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Spread out in rings from the start word, but find each word's neighbors by comparing it with every word in the list.

1. Put the start word in a waiting line (a queue). The ladder length is 1.
2. For each word in the current ring, compare it letter by letter with every unused word in the list. If they differ in exactly one letter, mark that word used and add it to the line.
3. When the end word comes out of the line, return the current length. After each ring, add 1.

class WordLadderCompare {
    public static int ladderLength(String begin, String end, List<String> words) {
        if (!words.contains(end)) return 0;
        Set<String> used = new HashSet<>();
        Queue<String> line = new ArrayDeque<>();
        line.add(begin);
        used.add(begin);
        int length = 1;                                // words in the ladder so far
        while (!line.isEmpty()) {
            int size = line.size();
            for (int i = 0; i < size; i++) {
                String word = line.poll();
                if (word.equals(end)) return length;
                for (String other : words) {           // compare with every word
                    if (!used.contains(other) && oneApart(word, other)) {
                        used.add(other);
                        line.add(other);
                    }
                }
            }
            length++;
        }
        return 0;
    }

    static boolean oneApart(String a, String b) {
        if (a.length() != b.length()) return false;
        int diff = 0;
        for (int i = 0; i < a.length() && diff < 2; i++) {
            if (a.charAt(i) != b.charAt(i)) diff++;
        }
        return diff == 1;
    }
}

How long it takes: each of the N words is compared with all N words, L letters each, O(N^2 * L). With 5,000 words that is 25 million comparisons. Extra room: the line and the used set, O(N * L).

Way 2: the clever way

Do not compare with every word. A word of length L has only 26 * L possible one-letter changes. Make each change and ask the jar (a hash set) if that word exists. When the list is big and the words are short, this is much faster.

1. Put all words in a jar (a set). If the end word is not there, return 0.
2. Put the start word in the line. The ladder length is 1.
3. For each word in the current ring: for each position, try all 26 letters. If the new word is in the jar, it is one jump away. If it is the end word, return length + 1. Otherwise take it out of the jar and add it to the line.
4. After each ring, add 1 to the length. If the line empties, return 0.

class WordLadderSwap {
    public static int ladderLength(String begin, String end, List<String> words) {
        Set<String> unused = new HashSet<>(words);     // words still in the jar
        if (!unused.contains(end)) return 0;
        unused.remove(begin);
        Queue<String> line = new ArrayDeque<>();
        line.add(begin);
        int length = 1;
        while (!line.isEmpty()) {
            int size = line.size();                    // everything in this ring
            for (int i = 0; i < size; i++) {
                char[] w = line.poll().toCharArray();
                for (int pos = 0; pos < w.length; pos++) {
                    char keep = w[pos];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == keep) continue;
                        w[pos] = c;
                        String next = new String(w);
                        if (!unused.contains(next)) continue;
                        if (next.equals(end)) return length + 1;
                        unused.remove(next);           // out of the jar: seen
                        line.add(next);
                    }
                    w[pos] = keep;                     // put the letter back
                }
            }
            length++;
        }
        return 0;
    }
}

How long it takes: each of the N words leaves the line once and tries 26 * L changes. Building and hashing each new word costs L, so O(26 * N * L^2). For short words and long lists this beats O(N^2 * L) by far. Extra room: the jar and the line, O(N * L).

Watch out for

• Return the number of words, not the number of changes. hit to cog is 5 words but 4 changes.
• Check that the end word is in the list before you start.
• The start word may not be in the list, and that is allowed. It is never needed again, so remove it from the jar if it is there.
• Count rings with the line's size at the start of each ring, not inside the loop.

What interviewers ask next

• Can you go faster? Search from both ends at once (bidirectional BFS), always growing the smaller side, and stop when the two sides touch. Each side only explores about half the depth, which often means far fewer words.
• Give back all shortest ladders (Word Ladder II). Run the BFS by rings and record, for each word, which words of the previous ring reach it. Then build every ladder by walking back from the end word with DFS.
• The alphabet is huge (like Unicode). Instead of trying 26 letters, group words by patterns with one letter hidden, like h*t, in a map. Words in the same group are one jump apart.
• What if changing some letters costs more than others? Then the jumps have weights, and Dijkstra's algorithm replaces the plain waiting line.

Remember this

Grown-up words: the words are vertices of an implicit graph, one-letter changes are edges, the ripples are BFS levels, the jar is a hash set used as the visited set, and searching from both ends is bidirectional BFS.