/126. Word Ladder II
Previous|Next

126. Word Ladder II

Hard
Hash Table27.6% acceptance

Given a start string start_word, a target string target_word, and a list of unique strings dictionary, each of the same length, find all shortest sequences of transformations from start_word to target_word. Each transformation changes exactly one character, and each intermediate word must be present in dictionary. Return all shortest transformation sequences as lists of strings, or an empty list if no such sequence exists. Each sequence must start with start_word and end with target_word.

Example 1

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

Output: [[lead,load,goad,gold]]

Explanation: lead -> load -> goad -> gold is the only shortest sequence.

Example 2

Input: start_word=game, target_word=code, dictionary=[came,cane,cone,code,gane,gone]

Output: [[game,gane,cane,cone,code]]

Explanation: game -> gane -> cane -> cone -> code is the only shortest sequence.

Example 3

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

Output: [[cold,cord,card,ward,warm]]

Explanation: cold -> cord -> card -> ward -> warm is the only shortest sequence.

Example 4

Input: start_word=play, target_word=stay, dictionary=[slay,stoy,stay,pray,plax]

Output: [[play,slay,stay]]

Explanation: play -> slay -> stay is the only shortest sequence.

Example 5

Input: start_word=rock, target_word=roll, dictionary=[rocl,rool,roll,rook,rack]

Output: [[rock,rocl,rool,roll]]

Explanation: rock -> rocl -> rool -> roll is the only shortest sequence.

Constraints

  • 1 <= len(start_word) <= 5
  • len(target_word) == len(start_word)
  • 1 <= len(dictionary) <= 500
  • All strings in dictionary have length equal to start_word
  • start_word, target_word, and all dictionary entries consist of lowercase English letters
  • start_word != target_word
  • All strings in dictionary are unique
  • The total number of all shortest transformation sequences does not exceed 105
Python (current runtime)

Case 1

Input: start_word='fast', target_word='slow', dictionary=['last','slat','slot','slow','flaw','flat']

Expected: [['fast','last','slat','slot','slow']]

Case 2

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

Expected: [['lamp','limp']]

Case 3

Input: start_word='moon', target_word='noon', dictionary=['noon','moan','mood','moon']

Expected: [['moon','noon']]

Case 4

Input: start_word='fire', target_word='hire', dictionary=['hire','fite','hite','fire']

Expected: [['fire','hire']]

Case 5

Input: start_word='blue', target_word='glue', dictionary=['glue','blve','blue','blge']

Expected: [['blue','glue']]