vvrf / DSA.log

问题拆解

在字符串里找出最长的回文子串。暴力做法是枚举所有 O(n²) 个子串，每个再花 O(n) 验证是否回文，总共 O(n³)。

暴力的浪费在于每次验证都从头做起，完全没有利用回文的结构。回文由中心决定：从中心向两边看，字符两两对称。反过来想，每一个回文子串都有一个中心——要么是某个字符（奇数长度），要么是某两个相邻字符的缝隙（偶数长度）。于是可以枚举中心而不是枚举子串：从每个中心向两侧扩展，直到字符不相等为止，扩出来的自然就是以该中心的最长回文。

长度为 n 的字符串只有 2n - 1 个可能的中心（n 个字符 + n - 1 个缝隙），每个中心扩展至多 O(n)，总时间 O(n²)——验证的成本被摊进了枚举本身。

另一条路是区间 DP：dp[i][j] 表示 s[i..j] 是否回文，由 dp[i+1][j-1] 加两端字符转移。时间同为 O(n²) 但空间要 O(n²)，本题中心扩展全面占优，DP 就不展开了。

中心扩展

最容易出错的是偶数长度的回文（如 "abba"）：它的中心不落在任何字符上。所以每个位置 i 要做两次扩展——以 (i, i) 为中心的奇数扩展和以 (i, i + 1) 为中心的偶数扩展，取两者较长。

public String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        int odd = expand(s, i, i);      // 奇数长度：中心是字符 i
        int even = expand(s, i, i + 1); // 偶数长度：中心是 i 和 i+1 的缝隙
        int len = Math.max(odd, even);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2; // 由中心和长度反推左端点
        }
    }
    return s.substring(start, start + maxLen);
}

// 从 (left, right) 向两侧扩，返回扩出的回文长度
private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1; // 循环多走了一步，回退
}

def longestPalindrome(s: str) -> str:
    def expand(left: int, right: int) -> int:
        # 从 (left, right) 向两侧扩，返回扩出的回文长度
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1  # 循环多走了一步，回退

    start, max_len = 0, 1
    for i in range(len(s)):
        odd = expand(i, i)       # 奇数长度：中心是字符 i
        even = expand(i, i + 1)  # 偶数长度：中心是 i 和 i+1 的缝隙
        length = max(odd, even)
        if length > max_len:
            max_len = length
            start = i - (length - 1) // 2  # 由中心和长度反推左端点
    return s[start:start + max_len]

func longestPalindrome(s string) string {
    // 从 (left, right) 向两侧扩，返回扩出的回文长度
    expand := func(left, right int) int {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return right - left - 1 // 循环多走了一步，回退
    }

    start, maxLen := 0, 1
    for i := 0; i < len(s); i++ {
        odd := expand(i, i)      // 奇数长度：中心是字符 i
        even := expand(i, i+1)   // 偶数长度：中心是 i 和 i+1 的缝隙
        length := max(odd, even)
        if length > maxLen {
            maxLen = length
            start = i - (length-1)/2 // 由中心和长度反推左端点
        }
    }
    return s[start : start+maxLen]
}

pub fn longest_palindrome(s: String) -> String {
    let bytes = s.as_bytes(); // 题目保证 ASCII，按字节比较即可
    let n = bytes.len();

    // 从 (left, right) 向两侧扩，返回扩出的回文长度；用 i64 避免 usize 下溢
    let expand = |mut left: i64, mut right: i64| -> i64 {
        while left >= 0 && right < n as i64 && bytes[left as usize] == bytes[right as usize] {
            left -= 1;
            right += 1;
        }
        right - left - 1 // 循环多走了一步，回退
    };

    let (mut start, mut max_len) = (0i64, 1i64);
    for i in 0..n as i64 {
        let odd = expand(i, i);      // 奇数长度：中心是字符 i
        let even = expand(i, i + 1); // 偶数长度：中心是 i 和 i+1 的缝隙
        let len = odd.max(even);
        if len > max_len {
            max_len = len;
            start = i - (len - 1) / 2; // 由中心和长度反推左端点
        }
    }
    s[start as usize..(start + max_len) as usize].to_string()
}

两个细节容易翻车。一是 expand 返回 right - left - 1：循环退出时 left 和 right 已经指向回文外侧第一个不匹配的位置，实际回文是 (left, right) 开区间，长度要减掉多走的两步再加一，化简正是这个式子。二是左端点公式 start = i - (len - 1) / 2 对奇偶两种情况恰好通用：奇数时 i 是正中心，偶数时 i 是中心偏左的那个字符，整数除法的向下取整正好吃掉了这半格偏移——不用分开讨论，但值得代入 "bb"（i = 0, len = 2）验证一遍。

复杂度

指标	复杂度	原因
时间	`O(n²)`	2n - 1 个中心，每个中心至多扩 O(n) 步
空间	`O(1)`	只记录最优区间的起点和长度

可以迁移的模式

判断/寻找回文优先想“从中心扩”而不是“从两端验”，回文子序列类才需要区间 DP；
枚举中心时别忘了偶数长度的“缝隙中心”，2n - 1 个中心一个都不能少；
扩展型循环退出后指针在合法区之外，返回值要做“回退一步”的换算。

中心扩展把回文的对称性直接编码进枚举顺序，同样的手法在“回文子串计数”（647）里可以原样复用。