## 1048. Longest String Chain

Given a list of words, each word consists of English lowercase letters.

Let's say `word1` is a predecessor of `word2` if and only if we can add exactly one letter anywhere in `word1` to make it equal to `word2`.  For example, `"abc"` is a predecessor of `"abac"`.

A word chain is a sequence of words `[word_1, word_2, ..., word_k]` with `k >= 1`, where `word_1` is a predecessor of `word_2`, `word_2` is a predecessor of `word_3`, and so on.

Return the longest possible length of a word chain with words chosen from the given list of `words`.

Example 1:

```Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".
```

Example 2:

```Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
```

Constraints:

• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 16`
• `words[i]` only consists of English lowercase letters.

## Rust Solution

``````struct Solution;

impl Solution {
fn is_prev(prev: &str, next: &str) -> bool {
let mut i = 0;
let mut j = 0;
while i < prev.len() {
if prev[i..=i] == next[j..=j] {
i += 1;
j += 1;
} else if i == j {
j += 1;
} else {
return false;
}
}
true
}
fn longest_str_chain(mut words: Vec<String>) -> i32 {
let n = words.len();
let mut v: Vec<i32> = vec![1; n];
let mut res = 1;
words.sort_unstable_by_key(|s| s.len());
for i in 1..n {
let cur = &words[i];
let m = cur.len();
for j in (0..i).rev() {
let l = words[j].len();
if l == m {
continue;
} else if l == m - 1 {
if Self::is_prev(&words[j], &words[i]) {
v[i] = v[j] + 1;
res = i32::max(res, v[i]);
break;
}
} else {
break;
}
}
}
res
}
}

#[test]
fn test() {
let words: Vec<String> = vec_string!["a", "b", "ba", "bca", "bda", "bdca"];
assert_eq!(Solution::longest_str_chain(words), 4);
let words: Vec<String> = vec_string![
"ksqvsyq",
"ks",
"kss",
"czvh",
"zczpzvdhx",
"zczpzvh",
"zczpzvhx",
"zcpzvh",
"zczvh",
"gr",
"grukmj",
"ksqvsq",
"gruj",
"kssq",
"ksqsq",
"grukkmj",
"grukj",
"zczpzfvdhx",
"gru"
];
assert_eq!(Solution::longest_str_chain(words), 7);
}
``````

Having problems with this solution? Click here to submit an issue on github.