Skip to content

5. 最长回文子串

Published: at 22:08

基本思路是:

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

简单想法是:

  1. 先有一个暴力版本,比如这道就是 O(n^3) 的循环版本
  2. 然后根据暴力版本,看哪里可以复用
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()
}
}

Previous Post
198. 打家劫舍