mediumDynamic Programming 1DPure DSA~25 min
Longest Word Chain by Single-Letter Insertions
A versioning scheme grows identifiers by inserting one character at a time. Given a vocabulary, find the longest chain where each word is a predecessor of the next via inserting exactly one letter.
Problem
Given a list words, wordA is a predecessor of wordB if inserting exactly one letter into wordA (without reordering the others) yields wordB. A word chain is a sequence where each word is a predecessor of the next. Return the length of the longest possible word chain.
Input
A list words of lowercase strings.
Output
An integer: the length of the longest word chain.
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 16
Examples
Example 1
Input
words = ["a","b","ba","bca","bda","bdca"]
Output
4
a -> ba -> bda -> bdca is a chain of length 4.
Example 2
Input
words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output
5
xb -> xbc -> cxbc -> pcxbc -> pcxbcf.