Problem overview
The method ladderLength takes beginWord, endWord and a list words. Each move changes one letter, and every word you step onto must be in the list. It returns how many words the shortest sequence contains, both ends included, or 0 when there is no sequence. All words share one length and use lowercase letters only.
For "hit" to "cog" with ["hot","dot","dog","lot","log","cog"], the shortest sequence is hit, hot, dot, dog, cog, so the answer is 5. Without "cog" in the list the answer is 0.
Approach: build the neighbors instead of searching for them
A breadth-first search (BFS) from beginWord finds the shortest sequence: it reaches every word one move away first, then two moves away, and so on. The first lesson on this problem finds the neighbors of a word by comparing it with every word in the list, which costs O(N · L) per word for N words of length L.
This lesson flips the question. A word of length L has only L × 25 possible one-letter changes. Instead of asking "which list words are close to this one?", generate each possible change and ask "is this in the list?". For that question to be fast, the list goes into a Set first, where a membership test takes constant time on average. The cost per word no longer depends on how long the list is, only on the word's length. That is a big win when the list is large and the words are short.
Step by step
- Build
wordSetwithSet(words). - Create the queue and a head index. The queue is an array. Instead of removing from its front, which shifts every other element, a variable
headmarks the next word to process. Words beforeheadare done, and the queue has work left exactly whilehead < queue.count. - Create
minDist, a dictionary from a word to the length of the shortest sequence reaching it. A word with an entry has been reached, so it doubles as the visited set. - Seed the search. Append
beginWordand give it distance 1: the answer counts words, so a one-word sequence has length 1. - Take the next word by reading
queue[head]intowordand then incrementinghead. - Stop at the target. BFS takes words out in order of distance, so when
endWordcomes out, its stored distance is the shortest. - Copy the word into a mutable character array
chars, then visit each positioni. - Save and restore. Remember
chars[i]inoriginal, try all letters at that position, then putoriginalback so the next position starts from the unchanged word. - Try every letter by looping over the character codes 97 to 122, which are
atoz, and writing the matching character intochars[i]. - Build
nextWordwithString(chars). - Filter. Skip it if the set doesn't contain it. Skip it if
minDistalready has an entry; this also skipsworditself, which appears when the letter tried equals the one already there. - Record and queue. Set its distance to
minDist[word]! + 1and append it. - Return
minDist[endWord] ?? 0.
The solution in Swift
class Solution {
func ladderLength(_ beginWord: String, _ endWord: String, _ words: [String]) -> Int {
let wordSet = Set(words)
var queue = [String]()
var head = 0
var minDist = [String: Int]()
queue.append(beginWord)
minDist[beginWord] = 1
while head < queue.count {
let word = queue[head]; head += 1
if endWord == word {
break
}
var chars = Array(word)
for i in 0..<chars.count {
let original = chars[i]
for c in 97...122 {
chars[i] = Character(UnicodeScalar(c)!)
let nextWord = String(chars)
if !wordSet.contains(nextWord) {
continue
}
if minDist[nextWord] != nil {
continue
}
minDist[nextWord] = minDist[word]! + 1
queue.append(nextWord)
}
chars[i] = original
}
}
return minDist[endWord] ?? 0
}
}
The Swift details worth knowing:
- Making a character from a number.
cis anInt.UnicodeScalar(c)returns an optional, because not every integer is a valid scalar, so the code force-unwraps it with!. For 97 to 122 that is always safe.Character(...)then wraps the scalar. Looping over the string"abcdefghijklmnopqrstuvwxyz"would give the characters directly. - Two statements on one line.
let word = queue[head]; head += 1uses a semicolon to separate them. Swift has no++operator, so the increment is+= 1. - Value types.
charsis avararray, so changingchars[i]changes only this array.String(chars)copies the characters into a new string each time, so earlier candidates are unaffected by later edits. Set(words)infersSet<String>from the array. Lookups withcontainsare constant time on average because strings are hashed.- Closed range.
97...122includes both ends, while0..<chars.countexcludes the end.
Complexity
Let N be the number of words and L the word length.
Time: O(N · L² · 26), which is O(N · L²) for the fixed 26-letter alphabet. Each word is expanded at most once. Expanding it tries L positions with 26 letters each, and every attempt builds a string and hashes it, both O(L).
Space: O(N · L). The set, the queue and the dictionary each hold up to about N strings of length L.
Compared with scanning the list for every word, which costs O(N² · L), this is better whenever N is much larger than 26 · L. For a tiny list with very long words the scanning version can be the cheaper one.
Edge cases and common mistakes
- Forgetting to restore the character. Without
chars[i] = original, the next position would start from a word that is already changed, and the search would generate words two letters away. - Looking only at the set, not at
minDist. Then words are queued again and again, and the search may never end on a list with a cycle of neighbors. - Start word not in the list. This is allowed.
"hit"to"hot"with["hot"]returns 2, becausebeginWordis queued directly and does not need to be in the set. - Target missing from the list. The set never contains it, so it is never reached and the result is 0.
- Counting changes, not words. Starting at distance 0 gives answers that are one too small.
- Uppercase or other characters. Only
atozare tried, which matches the problem's guarantee that words are lowercase.
Testing
"hit","cog",["hot","dot","dog","lot","log","cog"]gives5."hit","cog",["hot","dot","dog","lot","log"]gives0."hit","hot",["hot"]gives2."a","c",["a","b","c"]gives2.
