Longest String Chain
LC 1048 :)
The other question is shown in the img below:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
You are given an array of words where each word consists of lowercase English letters.
word₁ is a predecessor of word₂ if and only if we can insert exactly one letter anywhere in word₁ without changing the order of the other characters to make it equal to word₂.
For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcaa".
A word chain is a sequence of words [word₁, word₂, ..., wordₖ] with k >= 1, where word₁ is a predecessor of word₂, word₂ is a predecessor of word₃, and so on. A single word is trivially a word chain with k = 1.
Return the length of the longest possible word chain with words chosen from the given list of words.
words = ["a","b","ba","bca","bda","bdca"] return = 4
One of the longest word chains is ["a","ba","bda","bdca"].
words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] return = 5
All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
words = ["abcd","dbqca"] return = 1
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.
1 <= words.length <= 10001 <= words[i].length <= 16words[i]only consists of lowercase English letters.
public int longestStrChain(String[] words) {
// write your code here
}