946. Word Ladder Chain
A puzzle maker grows words one letter at a time. Word x can become word y if inserting exactly one letter at any position of x (without reordering its other letters) gives y.
From the list words pick some words and arrange them into a sequence where every word can become the next one. Words may be taken in any order from the list; a word that appears several times in the list counts once. A single word is a chain of length 1.
Return the length of the longest possible chain. Aim for time O(N * L^2) and extra space O(N * L), where N is the number of words and L their maximum length.
Example 1
- Input:
- words = ["qe","e","beet","bee","be","zz"]
- Output:
- 4
- Explanation:
Adding one letter at a time gives e, be, bee, beet, a chain of 4 words.
Example 2
- Input:
- words = ["tor","to","t","tour","or","our"]
- Output:
- 4
- Explanation:
The chain t, to, tor, tour has 4 words; or and our start a shorter chain.
Constraints
1 ≤ words.length ≤ 20000
1 ≤ words[i].length ≤ 12
Words consist of lowercase English letters.
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 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(N*L^2)
- Space
- O(N*L)