image.png
题目解析
- 采用中心分散发。
- 采用动态规划。
这里直接采用动态规划:
左右位置分别为 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)。
