基本思路是:
arr[i][j]
代表 区间是否为回文串arr[i][i]
= truearr[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) 的循环版本
- 然后根据暴力版本,看哪里可以复用
impl Solution { pub fn longest_palindrome(s: String) -> String { // arr[i][j] = longest_palindrome from str[i] to str[j] // arr[i][i + 1] = str[i] == str[i+1] ? true : false // arr[i + 1][j - 1] = arr[i][j] && str[i+1] == str[j-1] let len = s.len(); let mut arr = vec![vec![false; len]; len];
let mut max_start = 0; let mut max_end = 0; let mut max_len = 1;
// 我们要满足 i + 1 和 j - 1 下标的存在 // 所以 i 是 从 len 递减 // 而 j 则是从 i 开始递增(半三角形) for i in (0..len).rev() { for j in (i..len) { // 条件1: s[i] == s[j],回文串的长度可以扩展 if s.as_bytes()[i] == s.as_bytes()[j] { if j - i <= 1 { // 1个字符的相同/2个字符的相同 arr[i][j] = true; } else if arr[i + 1][j - 1] { // 3+ 个字符的相同,需要判断之前的状态 arr[i][j] = true; } }
// 保存最新的最长数据 if arr[i][j] && j - i + 1 > max_len { max_len = j - i + 1; max_start = i; max_end = j; } } }
(&s[max_start..max_end+1]).to_string() }}