题目链接
题目简介
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
示例 3：
输入：s = "a" 输出："a"
示例 4：
输入：s = "ac" 输出："a"
题目解析
- 该题目有两种做法：动态规划和中间扩散
- 对于动态规划来说：
- 我们使用
vis[i][j]来标记i~j之间的字符串是否为回文串 - 对于如何判断我们
i~j之间是否为回文串，我们去查看其vis[i + 1][j-1]是否为回文字符串 - 我们需要计算
j - 1 - i - 1 + 1 < 2 化简为 j - i < 3 - 最后不断更新
manLen和begin的值即可
- 对于中间扩散来说：
- 我们从中间来判断该字符串是否为回文串，依次进行扩散
- 在扩散的时候，需要考虑更新当前
begin和end的值 - 分别考虑偶数和奇数的情况
- 最后取最大值返回即可
题目代码
动态规划代码
public String longestPalindrome(String s) { if (s.length() < 2) { return s; } boolean[][] vis = new boolean[s.length()][s.length()]; int begin = 0; int maxLen = 1; for (int i = 0; i < s.length(); i++) { vis[i][i] = true; } for (int j = 0; j < s.length(); j++) { for (int i = 0; i < j; i++) { if (s.charAt(i) != s.charAt(j)) { vis[i][j] = false; } else { if (j - i < 3) { vis[i][j] = true; } else { vis[i][j] = vis[i + 1][j - 1]; } } if (vis[i][j] && j - i + 1> maxLen) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, maxLen); }
中心扩散代码
public String longestPalindrome1(String s) { int len = s.length(); if (len < 2) { return s; } int begin = 0; int end = 0; for (int i = 0; i < len; i++) { int left = judgmentString(s, i, i); int right = judgmentString(s, i, i + 1); int maxLen = Math.max(left, right); if (end - begin < maxLen) { begin = i - (maxLen - 1) / 2; end = i + maxLen / 2; } } return s.substring(begin, end + 1); } public int judgmentString(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - 1 - left; }
