题目
给你一个字符串
s，找到s中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
思路步骤：
- 初始化状态： 创建一个二维数组
dp，其中dp[i][j]表示字符串s从索引i到索引j的子串是否是回文串。初始化所有长度为 1 的子串为回文串。 - 处理长度为 2 的子串： 遍历字符串，检查相邻字符是否相等，如果相等则将
dp[i][i+1]设为true，表示长度为 2 的子串是回文串。 - 处理长度为 3 或更大的子串： 使用一个嵌套循环，外层循环控制子串的长度
len，内层循环遍历字符串，检查从索引i到索引j的子串是否是回文串。如果dp[i+1][j-1]为true且s.charAt(i) == s.charAt(j)，则说明当前子串也是回文串。 - 记录最长回文子串： 在内层循环中，如果发现新的回文子串长度比之前记录的最长回文子串更长，则更新
start和maxLength。 - 返回结果： 最终，返回最长回文子串
s.substring(start, start + maxLength)。
要使用动态规划解决这个问题，首先要定义状态和状态转移方程。在这里，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s 从索引 i 到索引 j 的子串是否是回文串。
代码
public class LongestPalindromeSubstring { public static String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } int n = s.length(); boolean[][] dp = new boolean[n][n]; int start = 0; int maxLength = 1; // All substrings of length 1 are palindromes for (int i = 0; i < n; i++) { dp[i][i] = true; } // Check substrings of length 2 for (int i = 0; i < n - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { dp[i][i + 1] = true; start = i; maxLength = 2; } } // Check substrings of length 3 or more for (int len = 3; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; // Ending index of the substring // Check if the substring is a palindrome and the inner substring is also a palindrome if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) { dp[i][j] = true; start = i; maxLength = len; } } } return s.substring(start, start + maxLength); } public static void main(String[] args) { String s1 = "babad"; String s2 = "cbbd"; System.out.println(longestPalindrome(s1)); // Output: "bab" or "aba" System.out.println(longestPalindrome(s2)); // Output: "bb" } }
