5. 最长回文子串

题目描述

输入一个字符串 s。回文串是正读和反读都一样的字符串。

在 s 的所有连续子串中，找出最长的回文子串并返回。如果有多个同样长的答案，返回其中任意一个即可。

示例 1

输入：s = "babad"
输出："bab"

解释："bab" 是长度为 3 的回文子串；"aba" 也同样合法。

示例 2

输入：s = "cbbd"
输出："bb"

解释：最长的回文子串是 "bb"。

数据范围

1 <= s.length <= 1000
s 只含数字和英文字母。

解题思路：中心扩展

以每个字符和每个缝隙为中心向外扩展，记录最长区间。

为什么正确

扩展时被接受的区间始终是回文，start、end 保存已检查区间中最长者，且所有中心都会被检查。

复杂度分析

时间 O(n²)，辅助空间 O(1)；返回子串切片另占 O(L) 输出空间，L 为答案长度。

易错点

奇数长度和偶数长度需要分别以字符和字符缝隙为中心检查。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = end = 0
        def expand(left: int, right: int) -> None:
            nonlocal start, end
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if right - left > end - start:
                    start, end = left, right
                left -= 1
                right += 1
        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)
        return s[start:end + 1]

class Solution {
    private String s;
    private int start, end;

    public String longestPalindrome(String s) {
        this.s = s;
        start = end = 0;
        for (int i = 0; i < s.length(); i++) {
            expand(i, i);
            expand(i, i + 1);
        }
        return s.substring(start, end + 1);
    }

    private void expand(int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            if (right - left > end - start) {
                start = left; end = right;
            }
            left--;
            right++;
        }
    }
}

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, end = 0;
        auto expand = [&](int left, int right) {
            while (left >= 0 && right < (int)s.size() && s[left] == s[right]) {
                if (right - left > end - start) {
                    start = left; end = right;
                }
                left--;
                right++;
            }
        };
        for (int i = 0; i < (int)s.size(); i++) {
            expand(i, i);
            expand(i, i + 1);
        }
        return s.substr(start, end - start + 1);
    }
};

func longestPalindrome(s string) string {
	start, end := 0, 0
	expand := func(left, right int) {
		for left >= 0 && right < len(s) && s[left] == s[right] {
			if right-left > end-start {
				start, end = left, right
			}
			left--
			right++
		}
	}
	for i := 0; i < len(s); i++ {
		expand(i, i)
		expand(i, i+1)
	}
	return s[start : end+1]
}

var longestPalindrome = function(s) {
    let start = 0, end = 0;
    const expand = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left > end - start) {
                start = left; end = right;
            }
            left--;
            right++;
        }
    };
    for (let i = 0; i < s.length; i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return s.slice(start, end + 1);
};

function longestPalindrome(s: string): string {
    let start = 0, end = 0;
    const expand = (left: number, right: number): void => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left > end - start) {
                start = left; end = right;
            }
            left--;
            right++;
        }
    };
    for (let i = 0; i < s.length; i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return s.slice(start, end + 1);
}

载入编辑器，自己跑一遍 →

其他解法

区间 DP 与中心扩展都是 O(n²)，中心扩展省去了 O(n²) 的表；Manacher 复用对称信息把时间降到 O(n)。

解法 2：区间动态规划时间 O(n²)，空间 O(n²)

dp[i][j] 表示 s[i..j] 是否为回文。按子串长度从小到大填表：两端字符相等，并且长度不超过 2 或内部 dp[i+1][j-1] 为真时，s[i..j] 是回文。每发现更长的回文就记录起点和长度。

状态定义清晰，是学习区间 DP 的入门例子。时间与中心扩展相同，却要 O(n²) 的表，实际运行也更慢。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        start, best = 0, 1
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and (length <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if length > best:
                        start, best = i, length
        return s[start:start + best]

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0, best = 1;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && (len <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (len > best) {
                        start = i;
                        best = len;
                    }
                }
            }
        }
        return s.substring(start, start + best);
    }
}

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int start = 0, best = 1;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && (len <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (len > best) {
                        start = i;
                        best = len;
                    }
                }
            }
        }
        return s.substr(start, best);
    }
};

func longestPalindrome(s string) string {
	n := len(s)
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	start, best := 0, 1
	for length := 1; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1
			if s[i] == s[j] && (length <= 2 || dp[i+1][j-1]) {
				dp[i][j] = true
				if length > best {
					start, best = i, length
				}
			}
		}
	}
	return s[start : start+best]
}

var longestPalindrome = function(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
    let start = 0, best = 1;
    for (let len = 1; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            if (s[i] === s[j] && (len <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (len > best) {
                    start = i;
                    best = len;
                }
            }
        }
    }
    return s.substring(start, start + best);
};

function longestPalindrome(s: string): string {
    const n = s.length;
    const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
    let start = 0, best = 1;
    for (let len = 1; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            if (s[i] === s[j] && (len <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (len > best) {
                    start = i;
                    best = len;
                }
            }
        }
    }
    return s.substring(start, start + best);
};

解法 3：Manacher 算法时间 O(n)，空间 O(n)

在字符之间插入 #，使奇偶回文统一为奇数长度。p[i] 记录以 i 为中心的最大臂长。维护已知右端最远的回文 [center-right, right]，若 i 在其内，就用对称点 2*center-i 的臂长给 p[i] 一个初值，再尝试继续向外扩展。转换串中的臂长正好是原串回文长度，起点为 (中心 - 臂长) / 2。

right 只增不减，整体线性时间，是本题的最优解。代码和正确性证明都更难，面试中一般写中心扩展即可。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = '#' + '#'.join(s) + '#'
        n = len(t)
        p = [0] * n
        center = right = 0
        best_c = best_r = 0
        for i in range(n):
            if i < right:
                p[i] = min(right - i, p[2 * center - i])
            while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
                p[i] += 1
            if i + p[i] > right:
                center, right = i, i + p[i]
            if p[i] > best_r:
                best_c, best_r = i, p[i]
        start = (best_c - best_r) // 2
        return s[start:start + best_r]

class Solution {
    public String longestPalindrome(String s) {
        StringBuilder sb = new StringBuilder("#");
        for (char c : s.toCharArray()) sb.append(c).append('#');
        String t = sb.toString();
        int n = t.length();
        int[] p = new int[n];
        int center = 0, right = 0, bestC = 0, bestR = 0;
        for (int i = 0; i < n; i++) {
            if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) p[i]++;
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            if (p[i] > bestR) {
                bestC = i;
                bestR = p[i];
            }
        }
        int start = (bestC - bestR) / 2;
        return s.substring(start, start + bestR);
    }
}

class Solution {
public:
    string longestPalindrome(string s) {
        string t = "#";
        for (char c : s) {
            t += c;
            t += '#';
        }
        int n = t.size();
        vector<int> p(n, 0);
        int center = 0, right = 0, bestC = 0, bestR = 0;
        for (int i = 0; i < n; i++) {
            if (i < right) p[i] = min(right - i, p[2 * center - i]);
            while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++;
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            if (p[i] > bestR) {
                bestC = i;
                bestR = p[i];
            }
        }
        return s.substr((bestC - bestR) / 2, bestR);
    }
};

func longestPalindrome(s string) string {
	t := make([]byte, 0, 2*len(s)+1)
	t = append(t, '#')
	for i := 0; i < len(s); i++ {
		t = append(t, s[i], '#')
	}
	n := len(t)
	p := make([]int, n)
	center, right, bestC, bestR := 0, 0, 0, 0
	for i := 0; i < n; i++ {
		if i < right {
			p[i] = min(right-i, p[2*center-i])
		}
		for i-p[i]-1 >= 0 && i+p[i]+1 < n && t[i-p[i]-1] == t[i+p[i]+1] {
			p[i]++
		}
		if i+p[i] > right {
			center, right = i, i+p[i]
		}
		if p[i] > bestR {
			bestC, bestR = i, p[i]
		}
	}
	start := (bestC - bestR) / 2
	return s[start : start+bestR]
}

var longestPalindrome = function(s) {
    const t = '#' + s.split('').join('#') + '#';
    const n = t.length;
    const p = new Array(n).fill(0);
    let center = 0, right = 0, bestC = 0, bestR = 0;
    for (let i = 0; i < n; i++) {
        if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] === t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        if (p[i] > bestR) {
            bestC = i;
            bestR = p[i];
        }
    }
    const start = (bestC - bestR) / 2;
    return s.substring(start, start + bestR);
};

function longestPalindrome(s: string): string {
    const t = '#' + s.split('').join('#') + '#';
    const n = t.length;
    const p: number[] = new Array(n).fill(0);
    let center = 0, right = 0, bestC = 0, bestR = 0;
    for (let i = 0; i < n; i++) {
        if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i - p[i] - 1] === t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        if (p[i] > bestR) {
            bestC = i;
            bestR = p[i];
        }
    }
    const start = (bestC - bestR) / 2;
    return s.substring(start, start + bestR);
};

动态规划专题的其他题目

查看动态规划全部题目 →