Funcia
Lv.2bfsgraphhashstring

Word Ladder Length

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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.
  • begin does not have to be in words.

Examples

begintargetwordsresult
"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

  • 1≤L=1 \le L = begin.length ≤10\le 10; target and every word in words also have length LL.
  • 1≤N=1 \le N = words.length ≤30,000\le 30{,}000; the words are distinct.
  • begin and target differ.
  • All strings consist of lowercase English letters.

Expected complexity

Time
O(N * L)
Space
O(N * L)

Examples

begintargetwordsExpected
"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 O(N2L)O(N^2 L) 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

LanguageEfficiency time limit
C (GCC, gnu17)518 msestimated
C++ (GCC, gnu++23)518 msderived
Python 3.131000 msderived
Java 251620 msderived
Kotlin 2.4 (JVM)2036 msestimated
C# 14 (.NET 10)2036 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.