Description
Given a list of words, find the longest string chain. Word A is a predecessor of B if you can insert exactly one letter anywhere in A to get B.
Examples
Input:
words = ["a","b","ba","bca","bda","bdca"]Output:
4Explanation:
Chain: "a" → "ba" → "bda" → "bdca".
Input:
words = ["word","world","w","wo","wor","worl"]Output:
5Explanation:
Chain: "w" → "wo" → "wor" → "worl" → "world". Each word is formed by inserting exactly one letter into the previous word. Note that "word" cannot continue the chain because it would require removing a letter from "world", not adding one.
Input:
words = ["cat","dog","bird","cats","dogs"]Output:
2Explanation:
The longest chains are "cat" → "cats" and "dog" → "dogs", each with length 2. "bird" stands alone with length 1. No word can be a predecessor to another except by adding 's' to form plurals.
Constraints
- •
1 ≤ words.length ≤ 1000 - •
1 ≤ words[i].length ≤ 16