Longest String Chain
Implement longestStrChain
Given a list of distinct lowercase words, find the length of the longest chain that can be built from them. A word continues the chain if it can be produced from the previous word by adding a single extra letter somewhere in the middle — the rest of the original spelling has to stay in the same relative sequence.
Framed in reverse, a word belongs right after whichever word remains once exactly one of its own letters is deleted. So the longest chain ending at any given word is just one more than the longest chain ending at the best such shorter word — provided that shorter word is actually present in the list. Since every predecessor is always exactly one letter shorter, processing the words from shortest to longest guarantees that by the time a word is reached, every string it could possibly extend has already been fully solved.
Example 1:
Input: words = ["o","t","to","ton","tan","tone"]
Output: 4
Example 2:
Input: words = ["xy","xay","xzay","wxzay","wxzayq"]
Output: 5
Example 3:
Input: words = ["abcd","dbqca"]
Output: 1
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ words.length ≤ 8 - ●
1 ≤ words[i].length ≤ 8 - ●
words[i] consists of lowercase English letters - ●
All the strings in words are distinct
words =
["o", "t", "to", "ton", "tan", "tone"]