最长回文子串

题目要求

编写一个算法来寻找给定字符串s中的最长回文子串。回文子串是指一个子串正读和反读都相同的字符串。如果存在多个长度相同的最长回文子串，返回任意一个即可。

解题思路

解决这个问题的关键是要理解回文的特性，以及如何高效地检查子串是否为回文。以下是几种可能的解题思路：

暴力法：检查字符串s的所有可能子串，判断它们是否为回文，并记录下最长的回文子串。这种方法的时间复杂度是 O(n^3)，因为需要 O(n^2)时间枚举所有子串，然后需要 O(n)时间来检查每个子串是否为回文。
动态规划：使用动态规划的方法，创建一个二维数组dp[i][j]，其中i和j表示字符串s的索引，dp[i][j]表示从索引i到j的子串是否为回文。通过状态转移方程来填充这个表格，可以在 O(n^2)时间内解决问题。
中心扩展法：考虑到回文串是对称的，我们可以选择一个中心点，向两边扩展来检查最长的回文子串。由于中心点可能是一个字符（奇数长度的回文串）或者两个字符之间的空隙（偶数长度的回文串），所以总共有2n-1个中心点。这种方法的时间复杂度是 O(n^2)。
Manacher 算法：这是一个专门用来寻找最长回文子串的线性时间算法（O(n)）。算法首先对原始字符串进行预处理，每个字符之间插入一个特殊字符（例如#），这样可以将奇数长度和偶数长度的回文串统一处理。然后使用一系列的指针来记录当前访问到的最右端的回文串的信息，以及这个回文串的中心位置，从而在遍历字符串的时候高效地更新最长回文子串的信息。

在实际应用中，中心扩展法通常是实现起来最简单的，而 Manacher 算法虽然最为高效，但实现起来较为复杂。根据具体情况选择合适的算法。

Golang 版本

package main

import "fmt"

func longestPalindrome(s string) string {
    if len(s) < 1 {
        return ""
    }

    start, end := 0, 0
    for i := 0; i < len(s); i++ {
        len1 := expandAroundCenter(s, i, i)
        len2 := expandAroundCenter(s, i, i+1)
        len := max(len1, len2)
        if len > end-start {
            start = i - (len-1)/2
            end = i + len/2
        }
    }
    return s[start : end+1]
}

func expandAroundCenter(s string, left, right int) int {
    L, R := left, right
    for L >= 0 && R < len(s) && s[L] == s[R] {
        L--
        R++
    }
    return R - L - 1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func main() {
    fmt.Println("The longest palindromic substring is:", longestPalindrome("babad"))
}

这段代码实现了中心扩展法。longestPalindrome函数找到并返回字符串s中的最长回文子串。expandAroundCenter函数用于给定中心进行扩展，检查以该中心为中心的最长回文子串的长度。max函数用于比较两个整数的大小。在main函数中，我们调用longestPalindrome函数并打印结果。

C++版本

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int n = s.size(), longestBegin = 0, maxLen = 1;
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    for (int i = 0; i < n; i++) {
        dp[i][i] = true; // 1 character is always a palindrome
    }

    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            longestBegin = i;
            maxLen = 2;
        }
    }

    for (int len = 3; len <= n; len++) { // check for lengths greater than 2
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                longestBegin = i;
                maxLen = len;
            }
        }
    }

    return s.substr(longestBegin, maxLen);
}

int main() {
    string s = "babad";
    cout << "The longest palindromic substring is: " << longestPalindrome(s) << endl;
    return 0;
}

这段代码使用了动态规划的方法来解决最长回文子串的问题。dp[i][j]表示子串s[i..j]是否为回文串。首先初始化长度为 1 和 2 的子串的回文状态，然后使用两层循环来填充整个dp表，外层循环控制子串的长度，内层循环控制子串的起始位置。如果一个子串的首尾字符相同，并且去掉首尾字符后的子串也是回文的，则该子串是回文的。每次找到更长的回文子串时，更新longestBegin和maxLen。最后，使用substr函数返回最长的回文子串。

Python 版本

def longest_palindrome(s: str) -> str:
    if len(s) == 0:
        return ""

    start = 0
    end = 0
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)
        len2 = expand_around_center(s, i, i + 1)
        max_len = max(len1, len2)
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2

    return s[start:end + 1]

def expand_around_center(s: str, left: int, right: int) -> int:
    L, R = left, right
    while L >= 0 and R < len(s) and s[L] == s[R]:
        L -= 1
        R += 1
    return R - L - 1

# Example usage:
if __name__ == "__main__":
    input_string = "babad"
    print("The longest palindromic substring is:", longest_palindrome(input_string))

这段 Python 代码实现了中心扩展法来找到最长的回文子串。longest_palindrome函数遍历每个字符，将其作为中心来扩展回文串。expand_around_center函数用于计算以left和right为中心的最长回文串的长度。最后，通过切片返回最长的回文子串。在主函数中，我们调用longest_palindrome函数并打印结果。

Java 版本

public class Solution {

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "babad";
        System.out.println("The longest palindromic substring is: " + solution.longestPalindrome(s));
    }
}

这段 Java 代码使用了中心扩展算法来找到最长的回文子串。longestPalindrome方法遍历字符串中的每个字符，并尝试将每个字符或两个相邻字符作为回文的中心，然后向两边扩展。expandAroundCenter方法用于找到以给定的中心能扩展出的最长回文的长度。最后，使用substring方法来获取并返回最长的回文子串。在main方法中，创建了Solution类的实例，并调用longestPalindrome方法来输出最长的回文子串。

Rust 版本

fn longest_palindrome(s: String) -> String {
    let chars: Vec<char> = s.chars().collect();
    let mut start = 0;
    let mut end = 0;

    for i in 0..chars.len() {
        let len1 = expand_around_center(&chars, i, i);
        let len2 = expand_around_center(&chars, i, i + 1);
        let len = len1.max(len2);
        if len > end - start {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }

    chars[start..=end].iter().collect()
}

fn expand_around_center(chars: &[char], mut left: usize, mut right: usize) -> usize {
    while left > 0 && right < chars.len() && chars[left] == chars[right] {
        if left > 0 { left -= 1; }
        right += 1;
    }
    if chars[left] != chars[right] { left += 1; } // Adjust left boundary if not matching
    right - left
}

fn main() {
    let input_string = "babad".to_string();
    println!("The longest palindromic substring is: {}", longest_palindrome(input_string));
}

这段 Rust 代码实现了寻找最长回文子串的功能。longest_palindrome函数首先将输入的字符串转换为字符数组，然后遍历每个字符，使用expand_around_center函数来找到以该字符为中心的最长回文子串的长度。expand_around_center函数负责向两边扩展，直到不再是回文为止。最后，使用数组切片语法和iter().collect()来构造并返回最长的回文子串。在main函数中，我们调用longest_palindrome函数并打印结果。

总结

上述代码示例中，无论是 Python、Java 还是 Rust 版本，核心算法都是基于中心扩展法来寻找最长回文子串。这种方法的基本思想是：

遍历字符串中的每个字符，将每个字符视为回文串的中心点。
对于每个中心点，考虑奇数长度和偶数长度的回文串两种情况，分别向两边扩展，直到不再满足回文条件。
在扩展过程中，记录并更新最长回文子串的起始和结束位置。
最后，根据记录的位置，提取并返回最长的回文子串。

不同语言的实现细节有所差异，但算法的核心逻辑是一致的。在 Python 和 Java 中，字符串可以直接通过索引访问和切片操作；而在 Rust 中，由于字符串的索引操作不同，需要将字符串转换为字符数组来进行操作。此外，Rust 的边界检查更为严格，需要额外注意索引操作时的边界条件。

这种中心扩展法的时间复杂度为 O(n^2)，其中 n 是输入字符串的长度。空间复杂度为 O(1)，因为除了输入字符串外，只需要常数空间来存储索引值。

hot-100