1048. Longest String Chain Medium

1/**
2 * [1048] Longest String Chain
3 *
4 * You are given an array of words where each word consists of lowercase English letters.
5 * wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.
6 * 
7 * 	For example, "abc" is a predecessor of "ab<u>a</u>c", while "cba" is not a predecessor of "bcad".
8 * 
9 * A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.
10 * Return the length of the longest possible word chain with words chosen from the given list of words.
11 *  
12 * Example 1:
13 * 
14 * Input: words = ["a","b","ba","bca","bda","bdca"]
15 * Output: 4
16 * Explanation: One of the longest word chains is ["a","<u>b</u>a","b<u>d</u>a","bd<u>c</u>a"].
17 * 
18 * Example 2:
19 * 
20 * Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
21 * Output: 5
22 * Explanation: All the words can be put in a word chain ["xb", "xb<u>c</u>", "<u>c</u>xbc", "<u>p</u>cxbc", "pcxbc<u>f</u>"].
23 * 
24 * Example 3:
25 * 
26 * Input: words = ["abcd","dbqca"]
27 * Output: 1
28 * Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
29 * ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	1 <= words.length <= 1000
35 * 	1 <= words[i].length <= 16
36 * 	words[i] only consists of lowercase English letters.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/longest-string-chain/
42// discuss: https://leetcode.com/problems/longest-string-chain/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn longest_str_chain(words: Vec<String>) -> i32 {
48        0
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_1048() {
60    }
61}
62