Start learning free

LESSON 369 OF 415 · GRAPHS

Word Ladder in Swift: BFS with a Wildcard Pattern Graph

Practice O(N * L²) Read the full explanation

Given two words (beginWord and endWord), and a list of words (words), find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
words = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
words = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in words, therefore no possible transformation.

STEP 1 OF 21

Guided

Ctrl + Enter to check

SWIFT · GRAPHS

Word Ladder in Swift, explained

Problem overview

The method ladderLength gets beginWord, endWord and a list words. A move changes exactly one letter, and each word you land on must be in the list. The method returns the number of words in the shortest sequence from beginWord to endWord, counting both, or 0 if none exists. All words have the same length and contain only lowercase letters.

With "hit", "cog" and ["hot","dot","dog","lot","log","cog"], the shortest sequence is hit, hot, dot, dog, cog: five words, so the answer is 5. Remove "cog" from the list and the answer is 0.

Approach: group words by wildcard pattern

Breadth-first search (BFS) finds the shortest sequence, as in the earlier lessons on this problem. What changes is how neighbors are found. Comparing a word with the whole list is slow. Generating all 25 changes per position works but builds many strings that aren't in the list.

This lesson uses an observation: two words differ in exactly one letter when they become the same string after one position is replaced with *. For example, hot and dot both turn into *ot, and hot and hit both turn into h*t. So build a dictionary, graph, that maps each pattern to the list of words that produce it. The neighbors of a word are the words stored under its own patterns, one pattern per position. No scanning and no wasted candidates are needed.

A pattern bucket holds at most 26 words, because words in one bucket differ only at one position and the list has no duplicates. That keeps every lookup short.

Step by step

Create graph as a [String: [String]].
Loop over the words and, inside, over every position i of the word.
Write getStarWord above ladderLength. It takes a word and a position, both unlabeled, and returns the word with that position replaced by *: the first i characters, then "*", then everything after position i.
Fill the graph. Inside the two loops, compute starWord and append the word to the list stored under it.
Prepare the search. Create the queue and the dictionary minDist (word to the length of the shortest sequence that reaches it, which also marks visited words). Append beginWord and set its distance to 1.
Loop while the queue is not empty and remove the front word.
Stop at the target. Words come out in order of distance, so when endWord is removed its distance is the shortest.
Visit each pattern of the word. For every position i, compute its starWord.
Visit the bucket. Loop over graph[starWord, default: []], naming each word nextWord.
Skip visited words. Only when minDist[nextWord] is nil do we continue. The word itself sits in its own bucket, but it already has an entry.
Record and queue. Set minDist[nextWord] to minDist[word]! + 1 and append nextWord.
Return minDist[endWord, default: 0].

The solution in Swift

class Solution {
    func getStarWord(_ word: String, _ i: Int) -> String {
        return String(word.prefix(i)) + "*" + String(word.dropFirst(i + 1))
    }

    func ladderLength(_ beginWord: String, _ endWord: String, _ words: [String]) -> Int {
        var graph: [String: [String]] = [:]
        for word in words {
            for i in 0..<word.count {
                let starWord = getStarWord(word, i)
                graph[starWord, default: []].append(word)
            }
        }
        var queue: [String] = []
        var minDist: [String: Int] = [:]
        queue.append(beginWord)
        minDist[beginWord] = 1
        while !queue.isEmpty {
            let word = queue.removeFirst()
            if endWord == word {
                break
            }
            for i in 0..<word.count {
                let starWord = getStarWord(word, i)
                for nextWord in graph[starWord, default: []] {
                    if minDist[nextWord] == nil {
                        minDist[nextWord] = minDist[word]! + 1
                        queue.append(nextWord)
                    }
                }
            }
        }
        return minDist[endWord, default: 0]
    }
}

The Swift details worth knowing:

Slicing a string by count. A string can't be indexed with an Int, but prefix(i) takes the first i characters and dropFirst(i + 1) skips i + 1 characters. Both return a Substring that shares storage with the original, so each is wrapped in String(...) before it is joined with +. For "hot" and i = 1 the result is "h*t".
The default: subscript. graph[key, default: []] reads the stored array, or an empty one for a missing key, without making the dictionary entry optional. Because it is also a setter, graph[key, default: []].append(word) creates the entry and appends in one statement.
Looping over a missing bucket. The same subscript makes a pattern that isn't in the graph loop zero times, which matters when beginWord isn't in the list.
Optional comparison. minDist[nextWord] == nil is true for a word not yet reached. minDist[word]! force-unwraps, which is safe because every queued word has an entry.
count on a string. It counts characters by walking the string, so it is O(L) and not a stored value. For lowercase ASCII words this equals the number of letters.
removeFirst() on an array shifts the remaining elements. It is fine at this size, though an index that moves along the array avoids the shifting.

Complexity

Let N be the number of words and L their length.

Time: O(N · L²). Building the graph creates L patterns per word, and each pattern costs O(L) to build and hash. The search expands each word once. It computes L patterns, and each pattern's bucket holds at most 26 words, so the work per word is again O(L²).

Space: O(N · L²). The graph holds up to N · L patterns, each a string of length L. The queue and minDist use O(N · L).

Edge cases and common mistakes

Start word not in the list. The search still works. beginWord never goes into the graph, but its patterns still match buckets of words that differ from it by one letter. "hit" to "hot" with ["hot"] gives 2.
Target missing. It never appears in any bucket, so it is never reached and the default 0 is returned.
Mixing up the dictionary default. The final lookup needs default: 0. Without it the value is optional and the method would not return an Int.
Forgetting the visited check. A word shares buckets with all its neighbors, so without the nil test it would be queued from every side, and the search would loop between neighbors forever.
Using the wrong pattern in the search. The search must use the same getStarWord as the build step, or the buckets won't match.
Counting changes, not words. The start distance is 1, not 0.

Testing

"hit", "cog", ["hot","dot","dog","lot","log","cog"] gives 5.
"hit", "cog", ["hot","dot","dog","lot","log"] gives 0.
"hit", "hot", ["hot"] gives 2.
"a", "c", ["a","b","c"] gives 2.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free