Word Ladder

You get a start word beginWord and a target word endWord. You also get a list words of allowed words.

Return the number of words in the shortest ladder from beginWord to endWord. Count both the start and the target. Return 0 if no ladder reaches the target.

A ladder follows two rules:

1. Each word differs from the word before it in exactly one letter.
2. Every word after the start is in words. The start word doesn't have to be.

Example 1:

Input:
beginWord = "cold",
endWord = "warm",
words = ["cord","card","ward","warm","worm","word","corm"]

Output: 5

Explanation: One letter changes at each step of this ladder:
"cold" -> "cord" -> "card" -> "ward" -> "warm"
This one is just as short:
"cold" -> "cord" -> "word" -> "worm" -> "warm"
Both have 5 words.

Example 2:

Input:
beginWord = "big"
endWord = "cup"
words = ["bag","bug","cup","cap"]

Output: 0

Explanation: "cup" is in the list, but no ladder reaches it.
From "big" you can only get to "bag" and "bug".
Neither of them is one letter away from "cap" or "cup".

Example 3:

Input:
beginWord = "sit"
endWord = "sat"
words = ["sat"]

Output: 2

Explanation: One change is enough: "sit" -> "sat".
The ladder has 2 words.

Constraints:

• The list has 1 to 5,000 words.
• No word appears twice in the list.
• All words have the same length, at most 10 letters. That includes beginWord and endWord.
• Every letter is a lowercase English letter.
• The words beginWord and endWord are different.