#1048
Longest String Chain
specialist · 665 · lc medium +30 · verified · 62.8% accepted · 7,779 likes · top 64%
Description
In the array words, word A is a predecessor of word B if inserting exactly one letter anywhere in A (without reordering) produces B.
- For example, "abc" is a predecessor of "abac".
A word chain is a sequence [word1, word2, ..., wordk] where each word is a predecessor of the next.
Return the length of the longest possible word chain using words from words.
Example 1:
Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].
Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
Example 3:
Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
Code
1
2
3