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.