本文共 1918 字，大约阅读时间需要 6 分钟。
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab” 解释：“aba” 同样是符合题意的答案。 示例 2：输入：s = “cbbd”
输出：“bb” 示例 3：输入：s = “a”
输出：“a” 示例 4：输入：s = “ac”
输出：“a”暴力求解
class Solution_5 { /** * 暴力求解 时间复杂度太高 * @param s * @return */ public String longestPalindrome(String s) { int n = s.length(); if (n < 2){ return s; } int maxLen = 1; int begin = 0; //s.charAt(i) 每次都会检查数组下标越界，因此可以先转换成字符数组 char[] chars = s.toCharArray(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (j - i - 1 > maxLen && validPalindromic(chars,i,j)){ maxLen = j - i + 1; begin = i; } } } return s.substring(begin,begin + maxLen); } /** * 验证子串s[left.length] 是否为回文串 */ private boolean validPalindromic(char[] charArray,int left,int right){ while (left < right){ if (charArray[left] != charArray[right]){ return false; } left++; right--; } return true; }} 动态规划
class Solution { public String longestPalindrome(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; String ans = ""; for (int l = 0; l < n; ++l) { for (int i = 0; i + l < n; ++i) { int j = i + l; if (l == 0) { dp[i][j] = true; } else if (l == 1) { dp[i][j] = (s.charAt(i) == s.charAt(j)); } else { dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]); } if (dp[i][j] && l + 1 > ans.length()) { ans = s.substring(i, i + l + 1); } } } return ans; }} 转载地址：http://mier.baihongyu.com/