Word Ladder Length
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Starting from the word begin, change exactly one letter at a time to reach the word target. Every intermediate word and
target itself must appear in the dictionary words.
Return the minimum number of words in the sequence, counting both ends, or 0 if target cannot be reached.
- All words have the same length and consist of lowercase English letters.
begindoes not have to be inwords.
Examples
| begin | target | words | result |
|---|---|---|---|
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log", "cog"] | 5 |
"hit" | "cog" | ["hot", "dot", "dog", "lot", "log"] | 0 |
"abc" | "abd" | ["abd"] | 2 |
Example 1 — hit → hot → dot → dog → cog uses 5 words.
Example 2 — cog is not in the dictionary.
Example 3 — One change is enough: abc, abd.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(begin: string, target: string, words: string[]) → int
Constraints
-
begin.length;targetand every word inwordsalso have length . -
words.length; the words are distinct. beginandtargetdiffer.- All strings consist of lowercase English letters.
Expected complexity
- Time
- O(N * L)
- Space
- O(N * L)
Examples
| begin | target | words | Expected |
|---|---|---|---|
"hit" | "cog" | ["hot","dot","dog","lot","log","cog"] | 5 |
"hit" | "cog" | ["hot","dot","dog","lot","log"] | 0 |
"abc" | "abd" | ["abd"] | 2 |
Hint
Hint
Run BFS over words, where two words are adjacent if they differ in one letter. Comparing the dequeued word with the whole
dictionary is and times out. Instead group words by wildcard patterns (h*t, *it, ...) in a hash map, or try all
26 letters at every position and look the result up in a hash set.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 518 ms | estimated |
| C++ (GCC, gnu++23) | 518 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1620 ms | derived |
| Kotlin 2.4 (JVM) | 2036 ms | estimated |
| C# 14 (.NET 10) | 2036 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |