55 lines
1.9 KiB
Rust
55 lines
1.9 KiB
Rust
impl Solution {
|
|
pub fn get_max_chain_len(from: &Vec<Vec<usize>>, memos: &mut Vec<i32>, start: usize) -> i32 {
|
|
let memo_val = *memos.get(start).unwrap_or(&-1);
|
|
if memo_val != -1 {
|
|
return memo_val;
|
|
}
|
|
let max_len = from.get(start)
|
|
.unwrap()
|
|
.iter()
|
|
.map(|&next| Solution::get_max_chain_len(from, memos, next))
|
|
.max()
|
|
.unwrap_or(0) + 1;
|
|
memos[start] = max_len;
|
|
max_len
|
|
}
|
|
#[inline]
|
|
pub fn is_predecessor(word: &String, of_word: &String) -> bool {
|
|
let mut skipped = false;
|
|
let mut oi = of_word.bytes();
|
|
of_word.len() == word.len() + 1 && word.bytes()
|
|
.all(|chr| {
|
|
if chr == oi.next().unwrap() { // Before extra character
|
|
true
|
|
} else if !skipped && chr == oi.next().unwrap() { // Extra character, skipped ensures this can only run once
|
|
skipped = true;
|
|
true
|
|
} else {
|
|
false
|
|
}
|
|
})
|
|
}
|
|
pub fn longest_str_chain(words: Vec<String>) -> i32 {
|
|
let (mut from, mut to) = (vec![vec![]; words.len()], vec![true; words.len()]);
|
|
for (idx1, w1) in words.iter().enumerate() {
|
|
for (idx2, w2) in words.iter().enumerate() {
|
|
if Solution::is_predecessor(w1, w2) {
|
|
from[idx1].push(idx2);
|
|
to[idx2] = false;
|
|
}
|
|
}
|
|
}
|
|
let mut memos = vec![-1; words.len()];
|
|
to.into_iter()
|
|
.enumerate()
|
|
.filter_map(|(to, froms)| {
|
|
if froms {
|
|
Some(Solution::get_max_chain_len(&from, &mut memos, to))
|
|
} else {
|
|
None
|
|
}
|
|
})
|
|
.max()
|
|
.unwrap()
|
|
}
|
|
} |