5. 最长回文子串 | Yesterday17's Blog

基本思路是：

arr[i][j] 代表 $[i, j]$ 区间是否为回文串
arr[i][i] = true
arr[i][i+1] = str[i] == str[i+1]
arr[i-1][j+1] = arr[i][j] && str[i-1] == str[j+1]

简单想法是：

先有一个暴力版本，比如这道就是 O(n^3) 的循环版本
然后根据暴力版本，看哪里可以复用

1
impl Solution {
2
    pub fn longest_palindrome(s: String) -> String {
3
        // arr[i][j] = longest_palindrome from str[i] to str[j]
4
        // arr[i][i + 1] = str[i] == str[i+1] ? true : false
5
        // arr[i + 1][j - 1] = arr[i][j] && str[i+1] == str[j-1]
6
        let len = s.len();
7
        let mut arr = vec![vec![false; len]; len];
8

9
        let mut max_start = 0;
10
        let mut max_end = 0;
11
        let mut max_len = 1;
12

13
        // 我们要满足 i + 1 和 j - 1 下标的存在
14
        // 所以 i 是 从 len 递减
15
        // 而 j 则是从 i 开始递增（半三角形）
16
        for i in (0..len).rev() {
17
            for j in (i..len) {
18
                // 条件1: s[i] == s[j]，回文串的长度可以扩展
19
                if s.as_bytes()[i] == s.as_bytes()[j] {
20
                    if j - i <= 1 { // 1个字符的相同/2个字符的相同
21
                        arr[i][j] = true;
22
                    } else if arr[i + 1][j - 1] { // 3+ 个字符的相同，需要判断之前的状态
23
                        arr[i][j] = true;
24
                    }
25
                }
26

27
                // 保存最新的最长数据
28
                if arr[i][j] && j - i + 1 > max_len {
29
                    max_len = j - i + 1;
30
                    max_start = i;
31
                    max_end = j;
32
                }
33
            }
34
        }
35

36
        (&s[max_start..max_end+1]).to_string()
37
    }
38
}