最长回文子串 - Rust

image.png

题目解析

1. 采用中心分散发。
2. 采用动态规划。
   这里直接采用动态规划:
   左右位置分别为 left ,right ， dp[left][right] 记录是否是回文字符串。如果 str[left] 和 str[right]的值相等，并且dp[left+1][right-1] = true,表示是一个回文字符串。

/// https://leetcode.cn/problems/longest-palindromic-substring/
pub fn longest_palindrome(s: String) -> String {
    let (mut start,mut end) = (0,0);
    let s = s.chars().collect::<Vec<_>>();
    let mut dp = vec![vec![false;s.len()];s.len()];
    for i in (0..s.len()).rev(){
        for j in i..s.len() {
            if i == j || j - i == 1 && s[i] == s[j]{
                dp[i][j] = true;
            }else {
                dp[i][j] = dp[i+1][j-1]&& s[i] == s[j]
            }
            if dp[i][j] && j-i > end-start {
                start = i;
                end = j;
            }
        }
    }
    s[start..=end].iter().collect()
}


#[cfg(test)]
mod tests {
   
    #[test]
    fn longest_palindrome_test() {
        use super::longest_palindrome;
        let s = String::from("babad");
        assert_eq!(String::from("bab"), longest_palindrome(s));
    }
}

复杂度分析
空间复杂度: O(n^2)。
时间复杂度: O(n^2)。