本文共 1918 字，大约阅读时间需要 6 分钟。

题目描述

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

示例 1：

输入：s = “babad”

输入：s = “cbbd”

输入：s = “a”

输入：s = “ac”

解题思路

暴力求解

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;    }}