• 动态规划

• 

class Solution {public String longestPalindrome(String s) {int len = s.length();// 特判if (len < 2){return s;}int maxLen = 1;int begin  = 0;// 1. 状态定义// dp[i][j] 表示s[i...j] 是否是回文串// 2. 初始化boolean[][] dp = new boolean[len][len];for (int i = 0; i < len; i++) {dp[i][i] = true;}char[] chars = s.toCharArray();// 3. 状态转移// 注意：先填左下角// 填表规则：先一列一列的填写，再一行一行的填，保证左下方的单元格先进行计算for (int j = 1;j < len;j++){for (int i = 0; i < j; i++) {// 头尾字符不相等，不是回文串if (chars[i] != chars[j]){dp[i][j] = false;}else {// 相等的情况下// 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串if (j - i < 3){dp[i][j] = true;}else {// 状态转移dp[i][j] = dp[i + 1][j - 1];}}// 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串// 此时更新记录回文长度和起始位置if (dp[i][j] && j - i + 1 > maxLen){maxLen = j - i + 1;begin = i;}}}// 4. 返回值return s.substring(begin,begin + maxLen);}
}

测试用例：

public static void main(String[] args) {Solution solution = new Solution();System.out.println(solution.longestPalindrome("babad"));}

• 时间复杂度： O(n^2) 两个for循环
• 空间复杂度： O(n^2) dp数组的大小

参考：

最长回文子串 - 最长回文子串 - 力扣（LeetCode） (leetcode-cn.com)

三种定义数组的格式如下：

int[] arr1=new int[10];int[] arr2={1,2,3,6};int[] arr3=new int[]{1,2,3,4,5,6,7,22};

数组的length是一个属性，而字符串的length()是一个方法了

arr1.length

s.length()

s.substring(i,j)

char [] dp=s.toCharArray()