LeetCode每日一题(516. Longest Palindromic Subsequence)

Given a string s, find the longest palindromic subsequence’s length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = “bbbab”
Output: 4

Explanation: One possible longest palindromic subsequence is “bbbb”.

Example 2:

Input: s = “cbbd”
Output: 2

Explanation: One possible longest palindromic subsequence is “bb”.

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

---

dp[i][j]代表 s[i…=j]中的回文的长度， 当我们找到一对儿相同的字符 s[i] == s[k], 如果我们要把这一对儿字符放到回文里，那最终回文长度就是 dp[i+1][k-1] + 2, 如果我们要略过这一对儿字符， 则是 dp[i+1][j]

---

use std::collections::HashMap;

impl Solution {
    
    fn dp(chars: &Vec<char>, i: usize, j: usize, cache: &mut HashMap<(usize, usize), i32>) -> i32 {
    
        if i > j {
    
            return 0;
        }
        if i == j {
    
            return 1;
        }
        let mut next_j = j;
        while i < next_j {
    
            if chars[i] != chars[next_j] {
    
                next_j -= 1;
                continue;
            }
            break;
        }
        let pick = if i == next_j {
    
            1
        } else {
    
            if let Some(c) = cache.get(&(i + 1, next_j - 1)) {
    
                *c + 2
            } else {
    
                Solution::dp(chars, i + 1, next_j - 1, cache) + 2
            }
        };
        let pass = if let Some(c) = cache.get(&(i + 1, j)) {
    
            *c
        } else {
    
            Solution::dp(chars, i + 1, j, cache)
        };
        let ans = pick.max(pass);
        cache.insert((i, j), ans);
        ans
    }

    pub fn longest_palindrome_subseq(s: String) -> i32 {
    
        let chars: Vec<char> = s.chars().collect();
        Solution::dp(&chars, 0, chars.len() - 1, &mut HashMap::new())
    }
}