LeetCode 5 最长回文子串 Rust实现函数签名 pub fn longest_palindrome(s: String) - String中心扩展法时间复杂度 O(n²)空间 O(1)工程常用也有Manacher O(n)下面给出中心扩展完整可提交版本。rustpub fn longest_palindrome(s: String) - String {let chars: Vecchar s.chars().collect();if chars.len() 1 {return s;}let mut start 0;let mut max_len 1;// 向两边扩展返回(回文长度)fn expand(chars: [char], l: usize, r: usize) - usize {let mut left l as isize;let mut right r as isize;while left 0 right chars.len() as isize chars[left as usize] chars[right as usize] {left - 1;right 1;}(right - left - 1) as usize}for i in 0..chars.len() {// 奇数长度回文let len1 expand(chars, i, i);// 偶数长度回文let len2 expand(chars, i, i 1);let cur_max len1.max(len2);if cur_max max_len {max_len cur_max;start i - (cur_max - 1) / 2;}}chars[start..start max_len].iter().collect()}#[cfg(test)]mod tests {use super::*;#[test]fn test() {assert!([bab.to_string(), aba.to_string()].contains(longest_palindrome(babad.to_string())));assert_eq!(longest_palindrome(cbbd.to_string()), bb);assert_eq!(longest_palindrome(a.to_string()), a);assert_eq!(longest_palindrome(ac.to_string()), a);}}Manacher算法 O(n) 版本可选更快rustpub fn longest_palindrome(s: String) - String {let chars: Vecchar s.chars().collect();if chars.is_empty() {return s;}// 预处理字符串插入#把奇偶统一let mut t vec![#];for c in chars {t.push(c);t.push(#);}let n t.len();let mut p vec![0; n];let mut center 0;let mut right 0;let mut max_p 0;let mut max_c 0;for i in 0..n {// 利用镜像加速let mirror 2 * center - i;if i right {p[i] p[mirror].min(right - i);}// 向外扩展while i p[i] 1 n i p[i]1 t[i p[i] 1] t[i - (p[i]1)] {p[i] 1;}// 更新中心与右边界if i p[i] right {center i;right i p[i];}if p[i] max_p {max_p p[i];max_c i;}}// 映射回原字符串下标let start (max_c - max_p)/2;chars[start..startmax_p].iter().collect()}复杂度- 中心扩展时间 O(n²)空间 O(1)- Manacher时间 O(n)空间 O(n)需要JS / Python / Java版本吗