670. Word Ladder Steps
A word-puzzle app turns one word into another by editing a single letter at a time. A move from word X to word Y is legal only when X and Y have the same length, differ in exactly one position, and Y appears in the list words. The starting word begin does not have to be in the list, and the same word may appear in the list more than once.
Return the minimum number of moves needed to change begin into end, counting each single-letter edit as one move. If end is not in words, or no chain of legal moves exists, return -1. The words are lowercase, all have the same length as begin, and if begin equals end the answer is 0 as long as that word is listed. With thousands of words, comparing every pair of words is too slow, so find a way to discover the neighbours of a word directly.
Example 1
- Input:
- begin = "cold"end = "warm"words = ["cord","card","ward","warm","core","wore"]
- Output:
- 4
- Explanation:
One shortest chain is cold, cord, card, ward, warm; all four letters differ between the endpoints, so fewer than 4 moves is impossible.
Example 2
- Input:
- begin = "lamp"end = "lime"words = ["limp","lamb","lump"]
- Output:
- -1
- Explanation:
The word
limeis not in the list, so it can never be reached and the answer is -1.
Constraints
1 ≤ length of each word ≤ 10
0 ≤ words.length ≤ 20000
all strings consist of lowercase English letters and share the same length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(N*L^2)
- Space
- O(N*L)