每日一题：5. 最长回文子串
package com.ljp.test.leetcode;
/**
-
<h2>5. 最长回文子串</h2>
-
<p>
-
给你一个字符串 s，找到 s 中最长的回文子串。
-
<p>
-
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
-
<p>
-
<p>
-
示例 1：
-
<p>
-
输入：s = "babad"
-
输出："bab"
-
解释："aba" 同样是符合题意的答案。
-
示例 2：
-
<p>
-
输入：s = "cbbd"
-
输出："bb"
-
<p>
-
提示：
-
<p>
-
1 <= s.length <= 1000
-
s 仅由数字和英文字母组成
-
<p>
-
来源：力扣（LeetCode）
-
链接：<a href="https://leetcode.cn/problems/longest-palindromic-substring">5. 最长回文子串</a>
-
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class Number0005 {public static void main(String[] args) {
String s1 = "babad";
String s2 = "cbbd";
String s3 = "abcddcbaefghjk";
String s4 = "a";
String s5 = "abcd";
System.out.println(DynamicPlanning.longestPalindromicSubstring(s1));
System.out.println(DynamicPlanning.longestPalindromicSubstring(s2));
System.out.println(DynamicPlanning.longestPalindromicSubstring(s3));
System.out.println(DynamicPlanning.longestPalindromicSubstring(s4));
System.out.println(DynamicPlanning.longestPalindromicSubstring(s5));
System.out.println("---------------------------------------------");
System.out.println(ExpandAroundCenter.longestPalindromicSubstring(s1));
System.out.println(ExpandAroundCenter.longestPalindromicSubstring(s2));
System.out.println(ExpandAroundCenter.longestPalindromicSubstring(s3));
System.out.println(ExpandAroundCenter.longestPalindromicSubstring(s4));
System.out.println(ExpandAroundCenter.longestPalindromicSubstring(s5));
}/**
-
动态规划
-
三大步骤：
-
1、定义数组元素的含义：result[i][j]=true，表示下标i到下标j是当前字符串的回文子串
-
2、找出数组元素之间的关系式：result[i+1][j-1]=true and chars[i]==char[j]=true，则result[i][j]=true
-
3、找出初始值：result[i][i]=true chars[i]==char[i+1]，则result[i][i+1]=true chars[i]==char[i+2]，则result[i][i+2]=true
*/
private static class DynamicPlanning {public static String longestPalindromicSubstring(String s) {
int length = s.length();
if (length == 1) return s;
boolean[][] result = new boolean[length][length];
// 最长回文字符串为1
for (int i = 0; i < length; i++) {
result[i][i] = true;
}
char[] chars = s.toCharArray();
int begin = 0, maxLength = 1;
// 最长回文字符串为2到length
for (int n = 2; n < length; n++) {
for (int i = 0; i < length; i++) {
int j = i + n - 1;
if (j >= length) {
break;
}
if (chars[i] != chars[j]) {
result[i][j] = false;
} else {
// 当子字符串长度为2和3时，必是子回文字符串
if (j - i < 3) {
result[i][j] = true;
} else {
result[i][j] = result[i + 1][j - 1];
}
}
if (result[i][j] && j - i + 1 > maxLength) {
begin = i;
maxLength = j - i + 1;
}
}
}
return s.substring(begin, begin + maxLength);
}
}
/**
-
中心扩展算法
*/
private static class ExpandAroundCenter {public static String longestPalindromicSubstring(String s) {
int length = s.length();
if (length == 1) return s;
int begin = 0, maxLength = 1;
for (int i = 0; i < length; i++) {
int l1 = expandAroundCenter(s, i, i);
int l2 = expandAroundCenter(s, i, i + 1);
int tempMaxLength = Math.max(l1, l2);
if (maxLength < tempMaxLength) {
maxLength = tempMaxLength;
begin = i - (maxLength - 1) / 2;
}
}
return s.substring(begin, begin + maxLength);
}private static int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// left多减了1，right多加了1.所以length=right-left+1-2=right-left-1
return right - left - 1;
}
}
-
}
