JAVA练习356- 最长回文子串

题目概览给你一个字符串s找到s中最长的 回文 子串。示例 1输入s babad输出bab解释aba 同样是符合题意的答案。示例 2输入s cbbd输出bb提示1 s.length 1000s仅由数字和英文字母组成来源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; } }