给你一个字符串 s,找到 s 中最长的回文子串。
- 示例 1:输入:s = “babad” 输出:”bab” 解释:”aba” 同样是符合题意的答案。
- 示例 2:输入:s = “cbbd” 输出:”bb”
- 示例 3:输入:s = “a” 输出:”a”
- 示例 4:输入:s = “ac” 输出:”a”
- 提示:1 <= s.length <= 1000 s 仅由数字和英文字母(大写和/或小写)组成
public class Test5 {
/**
* 先尝试穷举法1:判断每个字符开始和相同字符结束的串是否构成回文,若构成则继续判断下一个相同的字符
* 执行用时:450 ms, 在所有 Java 提交中击败了10.68%的用户内存消耗:39.1 MB, 在所有 Java 提交中击败了53.96%的用户
* @param s
* @return
*/
public String longestPalindrome(String s) {
//1、设置最长子串的长度
int maxLen = 1;
String result = s.charAt(0)+"";
System.out.println(s.length());
//2、循环处理每个字符串
for(int i=0;i<s.length();i++) {
//3、获取当前字符开头的子串
char now = s.charAt(i);
//4、判断后续与当前字符相同的字符,看啊可能是否能够构成回文,这里直接从后面开始判断
for(int j=i+1;j<s.length();j++) {
char next = s.charAt(j);
if(now==next) {
//检查这两个字符之间是否构成回文,也就是第一位等于最后一位
int num = j-i+1;//获取两个相同字符之间的字符数
if(num<=maxLen) {
//这里就没有必要判断这个了,不加这个回运行超时
continue;
}
int len =num/2;
boolean flag=true;
for(int k=0;k<len;k++) {
//检查是否是回文
if(s.charAt(i+k)!=s.charAt(j-k)) {
//不是回文
flag=false;
break;
}
}
if(flag) {
//这里表明从i到j是回文,长度为len
System.out.println("从下标"+i+"到"+j+"构成回文:"+s.substring(i, j+1)+"长度为"+num);
if(num>maxLen) {
maxLen=num;
result=s.substring(i, j+1);
}
}
}
}
}
return result;
}
/**
* 先尝试穷举法2:穷举法1会导致同一个字符多次判断,比如abababa那边后面三个a都要判断,但是加入从后面往前判断就只需要判断最后一个a
* 这种方式比第一种效果好一点
* 执行用时:398 ms, 在所有 Java 提交中击败了13.99%的用户内存消耗:38.7 MB, 在所有 Java 提交中击败了65.25%的用户
* @param s
* @return
*/
public String longestPalindrome2(String s) {
//1、设置最长子串的长度
int maxLen = 1;
int start_i=0;//开始下标
int end_i=0;//结束下标
//2、循环处理每个字符串
for(int i=0;i<s.length();i++) {
//3、获取当前字符开头的子串
char now = s.charAt(i);
//4、判断后续与当前字符相同的字符,看啊可能是否能够构成回文,这里直接从后面开始判断
for(int j=s.length()-1;j>i;j--) {
char next = s.charAt(j);
if(now==next) {
//检查这两个字符之间是否构成回文,也就是第一位等于最后一位
int num = j-i+1;//获取两个相同字符之间的字符数
if(num<=maxLen) {
//这里就没有必要判断这个了,不加这个回运行超时
continue;
}
int len =num/2;
boolean flag=true;
for(int k=0;k<len;k++) {
//检查是否是回文
if(s.charAt(i+k)!=s.charAt(j-k)) {
//不是回文
flag=false;
break;
}
}
if(flag) {
//这里表明从i到j是回文,长度为len
//System.out.println("从下标"+i+"到"+j+"构成回文:"+s.substring(i, j+1)+"长度为"+num);
if(num>maxLen) {
maxLen=num;
start_i=i;
end_i=j;
//result=s.substring(i, j+1);
}
//这里如果有回文,直接判断下一个字符
continue;
}
}
}
}
String result = s.substring(start_i, end_i+1);
System.out.println("最大回文长度为:"+((end_i-start_i)+1)+"回文串为:"+result);
return result;
}
/**
* 一维动态规划法:我他喵,果然比我的好很多
* 执行用时:17 ms, 在所有 Java 提交中击败了91.19%的用户内存消耗:38.6 MB, 在所有 Java 提交中击败了72.87%的用户
* @param s
* @return
*/
public String longestPalindrome3(String s) {
int n = s.length();
// dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
// 其长度就是 j - dp[j] + 1
int[] dp = new int[n];
dp[0] = 0;
// 记录最大回文子串的长度
// 0 - 0 + 1
int max_length = 1;
int start_i=0;//开始下标
int end_i=0;//结束下标
for (int j = 1; j < n; j++) {
if (dp[j - 1] > 0 && s.charAt(j) == s.charAt(dp[j - 1] - 1)) {
// 当前位置的字符和上一次回文串的左邻字符相同
// 回文串得到扩展
dp[j] = dp[j - 1] - 1;
} else {
// 从左向右找
int left = dp[j - 1];
int right = j;
int start = left; // 最近一次的回文查找起始位置
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
// 遭遇失配字符,重置 right
right = j;
start = left + 1;
} else {
// 否则,两边继续收拢
right--;
}
left++;
}
dp[j] = start;
}
// 更新最大值
int length = j - dp[j] + 1;
if (length > max_length) {
max_length = length;
end_i=j;
start_i=dp[j];
}
}
String result = s.substring(start_i, end_i+1);
System.out.println("最大回文长度为:"+((end_i-start_i)+1)+"回文串为:"+result);
return result;
}
/**
* 二维动态规划法:还是一维动态规划厉害
* 执行用时:311 ms, 在所有 Java 提交中击败了27.99%的用户内存消耗:42.4 MB, 在所有 Java 提交中击败了37.71%的用户
* @param s
* @return
*
*/
public String longestPalindrome4(String s) {
int n = s.length();
// dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
// 其长度就是 j - dp[j] + 1
// 记录最大回文子串的长度
// 0 - 0 + 1
int max_length = 1;
int start_i=0;//开始下标
int end_i=0;//结束下标
// dp[i][j] 表示 s[i..j] 是否回文,j >= i
boolean[][] dp=new boolean[n][n];
// 初始化
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) dp[i][j] = false;
// 易知,单个字符 s[i..i] 构成回文
for (int i = 0; i < n; i++) dp[i][i] = true;
// 记录最大回文子串的长度,至少为 1
// 考虑递推
// 主要的递推关系是 dp[i][j] = dp[i+1][j-1]
// 所以倒序遍历 i ,才可以形成递推
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s.charAt(i)== s.charAt(j)) {
if (j - 1 >= i + 1) { // 子串 s[i+1..j-1] 有效性
if (dp[i + 1][j - 1]) dp[i][j] = true;
} else {
// 此时 j < i + 2 即 j <= i+1
// 再之 s[i] == s[j],必回文
dp[i][j] = true;
}
}
if (dp[i][j]) {
// 更新最大长度
int length = j - i + 1;
if (length > max_length) {
max_length = length;
end_i=j;
start_i=i;
}
}
}
}
String result = s.substring(start_i, end_i+1);
System.out.println("最大回文长度为:"+((end_i-start_i)+1)+"回文串为:"+result);
return result;
}
public static void main(String[] args) {
//String result = new Test5().longestPalindrome2("1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111");
//String result = new Test5().longestPalindrome3("abaasasdasd");
String result = new Test5().longestPalindrome4("acbcbcbc");
System.out.println("result:"+result);
}
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
参考:动态规划部分:https://writings.sh/post/algorithm-longest-palindromic-substring