Start learning free

LESSON 367 OF 415 · GRAPHS

Word Ladder in Swift: BFS Comparing Every Word Pair

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 16

Guided

Ctrl + Enter to check

SWIFT · GRAPHS

Word Ladder in Swift, explained

Problem overview

The method ladderLength receives a start word beginWord, a target endWord and a list words. A move changes exactly one letter, and every word you land on must be in words. The method returns the number of words in the shortest sequence from beginWord to endWord, counting both ends, or 0 when no sequence exists. All words have the same length and use lowercase letters.

With beginWord = "hit", endWord = "cog" and words = ["hot","dot","dog","lot","log","cog"], the shortest sequence is hit, hot, dot, dog, cog. That is five words, so the answer is 5. If cog is missing from the list, no sequence can end there and the answer is 0.

Approach: breadth-first search over words

Think of every word as a vertex and draw an edge between two words that differ in exactly one position. The question becomes: how many vertices are on the shortest path from beginWord to endWord? Breadth-first search (BFS) answers that. It visits all words one move away, then all words two moves away, and so on, so the first time it reaches a word is along a shortest path.

BFS needs two things: a queue of words waiting to be expanded, and a record of words already reached, so none is queued twice. This lesson uses one dictionary, minDist, for both jobs. It maps a word to the length of the shortest sequence that reaches it, and a word with an entry has been reached.

The simplest way to find the neighbors of a word is to compare it with every word in the list and keep those that differ in exactly one position. That costs a lot per word, but it needs no extra data structure. Later lessons on this problem speed it up.

Step by step

Create the queue as an empty [String].
Create minDist as an empty [String: Int].
Start at beginWord. Append it to the queue and set its distance to 1. The answer counts words, not changes, so a sequence of one word has length 1.
Loop while the queue is not empty.
Remove the front word into word.
Stop at the target. BFS removes words in order of distance, so when endWord comes out, its stored distance is already the shortest one. Break out of the loop.
Scan the list. For every nextWord in words, decide whether it is a valid next step.
Require exactly one difference. The helper numOfChanges counts differing positions. A count of 0 means the same word, and 2 or more means too far away, so skip everything that isn't 1.
Skip words already reached. If minDist[nextWord] is not nil, an earlier path got there at least as quickly.
Record and queue. Otherwise set minDist[nextWord] to minDist[word]! + 1 and append it to the queue.
Return the answer as minDist[endWord] ?? 0, which is 0 when the target was never reached.
Write numOfChanges with two unlabeled String parameters. It turns both into character arrays, loops over the positions and counts those where the characters differ.

The solution in Swift

class Solution {
    func numOfChanges(_ first: String, _ second: String) -> Int {
        let a = Array(first)
        let b = Array(second)
        var differences = 0
        for i in 0..<a.count {
            if a[i] != b[i] {
                differences += 1
            }
        }
        return differences
    }

    func ladderLength(_ beginWord: String, _ endWord: String, _ words: [String]) -> Int {
        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 nextWord in words {
                if numOfChanges(word, nextWord) != 1 {
                    continue
                }
                if minDist[nextWord] != nil {
                    continue
                }
                minDist[nextWord] = minDist[word]! + 1
                queue.append(nextWord)
            }
        }
        return minDist[endWord] ?? 0
    }
}

The Swift details worth knowing:

No integer indexing on strings. first[0] doesn't compile, because a Swift String is a sequence of characters with variable width, not an array. Array(first) builds a [Character] that can be indexed with an Int.
Same length assumed. The loop runs to a.count and reads b[i], so a second shorter than first would crash with an index-out-of-range error. The problem guarantees equal lengths.
Dictionary lookups are optional. minDist[nextWord] has type Int?, and it is nil for a missing key. Comparing it with nil tests whether the word was reached. minDist[word]! force-unwraps, which is safe because every queued word got an entry before it was queued, and crashes if the entry is missing.
?? returns the left side when it has a value and the right side otherwise. minDist[endWord] ?? 0 turns "never reached" into the required 0.
removeFirst() removes and returns the first element of the array. On an array it shifts every remaining element, so it costs time proportional to the queue length.
0..<a.count is a half-open range: it includes 0 and stops before a.count, which are exactly the valid indices.

Complexity

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

Time: O(N² · L). Each word enters the queue at most once, so at most N + 1 words are expanded. Expanding a word compares it with all N list words, and each comparison turns two strings into arrays and scans them in O(L). The shifting done by removeFirst() adds at most O(N) per removal, which is smaller.

Space: O(N · L). The queue and the dictionary hold at most N + 1 strings of length L.

Edge cases and common mistakes

Target missing from the list. The BFS never reaches endWord, so minDist[endWord] is nil and the method returns 0.
Start word not in the list. This is allowed. beginWord goes into the queue directly, and only the words it moves to must be in words. With beginWord = "hit", endWord = "hot" and words = ["hot"], the answer is 2.
Counting changes instead of words. Starting the distance at 0 makes every answer one too small.
Accepting zero differences. If the check were numOfChanges(...) > 1, a word would count as its own neighbor. It is harmless here only because the visited check catches it.
Marking words as reached when they leave the queue instead of when they enter it. The same word can then be queued many times.
Stopping at the first sighting. Breaking out of the loop at the moment endWord is discovered also works, but this solution waits until it is removed. Both are correct for BFS.

Testing

beginWord = "hit", endWord = "cog", words = ["hot","dot","dog","lot","log","cog"] gives 5.
The same words without "cog" give 0.
beginWord = "hit", endWord = "hot", words = ["hot"] gives 2.
beginWord = "hot", endWord = "dot", words = ["dot"] 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