力扣第五题——最长回文字符串

题目介绍

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

完整代码

public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;boolean[][] dp = new boolean[len][len];for (int i = 0; i < len; i++) {dp[i][i] = true;}char[] charArray = s.toCharArray();for (int L = 2; L <= len; L++) {for (int i = 0; i < len; i++) {int j = L + i - 1;if (j >= len) {break;}if (charArray[i] != charArray[j]) {dp[i][j] = false;} else {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}
}

 代码思路

这段代码是用来寻找字符串中最长回文子串的解决方案。以下是代码的思路：
1. **初始化变量**：
   - `len`：表示输入字符串`s`的长度。
   - `maxLen`：记录最长回文子串的长度，初始值为1。
   - `begin`：记录最长回文子串的起始位置，初始值为0。
   - `dp`：一个二维布尔数组，用于记录子串`s[i...j]`是否为回文串。
2. **边界条件处理**：
   - 如果字符串长度小于2，直接返回原字符串，因为单个字符或空字符串本身就是回文串。
3. **初始化dp数组**：
   - 对于所有单个字符，它们肯定是回文串，因此将`dp[i][i]`设置为`true`。
4. **遍历子串长度**：
   - 从长度为2的子串开始，依次遍历所有可能的子串长度（2到len）。
5. **内层循环**：
   - 对于每个子串长度，使用两个指针`i`和`j`分别表示子串的起始和结束位置。
   - 如果`j`超出字符串长度，则跳出当前循环。
6. **判断子串是否为回文**：
   - 如果子串的首尾字符不相等，则该子串不是回文串，将`dp[i][j]`设置为`false`。
   - 如果首尾字符相等，分两种情况：
     - 如果子串长度小于等于3，由于首尾字符相等，该子串必定是回文串，将`dp[i][j]`设置为`true`。
     - 如果子串长度大于3，需要判断去掉首尾字符后的子串是否为回文串，即`dp[i+1][j-1]`。
7. **更新最长回文子串**：
   - 如果当前子串是回文串且长度大于`maxLen`，则更新`maxLen`和`begin`。
8. **返回结果**：
   - 根据记录的起始位置`begin`和最长长度`maxLen`，返回最长回文子串。
通过动态规划的方法，该代码有效地解决了寻找最长回文子串的问题。时间复杂度为O(n^2)，空间复杂度也为O(n^2)。