企业官网建设流程全解析

题目概览

给你一个字符串s，找到s中最长的 回文 子串。

示例 1：

输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s仅由数字和英文字母组成

来源：5. 最长回文子串 - 力扣（LeetCode）

解题分析

方法：动态规划

令回文子串的起始和结束索引为 i 和 j，那么 Si 一定等于 Sj，我们可以得到状态转移方程：

S(i, j) = Si + S(i-1, j-1) + Sj ( Si == Sj )

因此我们定义一个方法将当前回文子串进行扩展，判断 i - 1 和 j + 1 的字符是否一致，一致则继续扩展，得到最大的回文子串。当前回文子串可以为当前字母，也可能为空字符串，因此两个都要扩展并取到最大值。

遍历字符串，按照以上方式挨个找最大的回文子串即可。

时间复杂度：O(n²)
空间复杂度：O(1)

class Solution { public String longestPalindrome(String s) { int start = 0, end = 1; for (int i = 1; i < s.length(); ++i) { int len = Math.max(findMaxLen(s, i, i), findMaxLen(s, i-1, i)); if (len > end - start) { start = i - len / 2; end = start + len; } } return s.substring(start, end); } public int findMaxLen(String s, int start, int end) { while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) { start--; end++; } return end - start - 1; } }