/127. Word Ladder
Previous|Next

127. Word Ladder

Hard
Hash Table45% acceptance

Given a start string start_word, a target string target_word, and a list of strings dictionary, find the minimum number of strings in a sequence starting with start_word and ending with target_word such that each consecutive pair of strings in the sequence differs by exactly one character, and every intermediate string (excluding start_word) is present in dictionary. Return 0 if no such sequence exists.

Example 1

Input: start_word=lead, target_word=gold, dictionary=[load,goad,gold,gald]

Output: 4

Explanation: lead -> load -> goad -> gold

Example 2

Input: start_word=game, target_word=math, dictionary=[fame,mate,math,gate]

Output: 0

Explanation: No valid sequence exists as math cannot be reached by single-letter changes.

Example 3

Input: start_word=cold, target_word=warm, dictionary=[cord,card,ward,warm,worm]

Output: 5

Explanation: cold -> cord -> card -> ward -> warm

Constraints

  • 1 <= len(start_word) <= 10
  • len(target_word) == len(start_word)
  • 1 <= len(dictionary) <= 5000
  • All strings in dictionary have length equal to start_word
  • start_word, target_word, and all dictionary strings consist of lowercase English letters
  • start_word != target_word
  • All strings in dictionary are unique
Python (current runtime)

Case 1

Input: start_word='spin', target_word='spot', dictionary=['spit','spat','spot','span']

Expected: 4

Case 2

Input: start_word='tone', target_word='tune', dictionary=['tome','tune','tine']

Expected: 3

Case 3

Input: start_word='rock', target_word='roll', dictionary=['rook','rool','roll','rokl']

Expected: 4

Case 4

Input: start_word='fast', target_word='slow', dictionary=['last','slaw','slow','flaw']

Expected: 0

Case 5

Input: start_word='lamp', target_word='limp', dictionary=['limp','lump','lamp']

Expected: 2