Dodomeki
Sign in

109. Word Ladder

Hard

Given words inicio and fim with the same length and a dictionary, at each step change exactly one letter and use only words present in the dictionary. Return the number of words in the shortest sequence that starts at inicio and ends at fim, counting both endpoints; return 0 if no such sequence exists.

Example 1
Input: inicio = "gato", fim = "rato", palavras = ["rato","riso","rido","gido","gato"]
Output: 2
Example 2
Input: inicio = "casa", fim = "casa", palavras = ["casa"]
Output: 1
Constraints
  • 1 <= tamanho das palavras <= 10
  • 1 <= palavras.length <= 5000
  • Todas as palavras têm o mesmo tamanho.
  • As palavras contêm apenas letras minúsculas de a a z.
GraphsBFSStrings
Caso 1
inicio =
"gato"
fim =
"rato"
palavras =
["rato","riso","rido","gido","gato"]
Expected =
2
Caso 2
inicio =
"casa"
fim =
"casa"
palavras =
["casa"]
Expected =
1

Run checks these 2 cases. Submit runs all 6, including hidden ones.