算法练习——最长回文子串
2021-07-04 14:05
标签：判断字符串 splay 最长公共子序列 span max div maxlength size 矩阵 题目： 给定一个字符串 s，找到 s 中最长的回文子串。 示例 1： 示例 2： 思路：可以通从两端到中间遍历字符串，如果碰到字符串是回文串，则该回文串一定是是最长回文串。 效果：判断的整个过程其实有三个内部循环，时间复杂度接近 O(n^3) ，空间复杂度O(n) 思路：如果s(i,j)是回文串，则table[i][j] = true;否则定义为false。如何计算table[i][j]呢，我们可以首先检查table[i+1][j-1]是否为true，及s[i]是否等于s[j]。 --------------------------------------------------这个思想其实和前面的求解最长公共子序列很像。 效果：时间复杂度O(n^2),空间O(n^2) 思路：以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。 奇数有一个中心，偶数有两个中心点，从中心点向两端判断，找出最长的回文子串。 效果：时间复杂度O(n^2)，空间O(1) 算法练习——最长回文子串 标签：判断字符串 splay 最长公共子序列 span max div maxlength size 矩阵 原文地址：https://www.cnblogs.com/xiaxj/p/9613842.html输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
输入: "cbbd"
输出: "bb"
方法1：暴力求解
public class LongestPalindrome1 {
//利用两个for循环来遍历所有的子串，并且在里面再加一层while循环用于判断字符串是否是回文串
public String longestPalindrome(String s) {
for (int size = s.length(); size > 0; size--) {
for (int low = 0, hight = low+size-1; hight ) {
if (isPalindrome(s,low,hight)) {
return s.substring(low, hight+1);
}
}
}
return s.substring(0, 1);
}
//判断一个字符串是否是回文字符
private boolean isPalindrome(String s, int low, int hight) {
while (low hight) {
if(s.charAt(low) == s.charAt(hight)){
low++;
hight--;
}else {
return false;
}
}
return true;
}
}
方法2：动态规划思想
public class LongestPalindrome {
public static String longestPalSubstr(String s){
int n = s.length();
boolean[][] table = new boolean[n][n];
//所有的一个字符肯定是回文串
int maxLength = 1;
//组成的boolean矩阵的对角都肯定为true
for (int i = 0; i ) {
table[i][i] = true;
}
int start = 0;
//如果字符串长度小于2，则直接处理
for (int i = 0; i i) {
if (s.charAt(i) == s.charAt(i +1)) {
table[i][i+1] = true;
start = i;
maxLength = 2;
}
}
//如果字符串长度大于2，则开始遍历处理，主要是通过两层for循环
//检查字符串长度大于2的字符串，其中k表示子字符串的长度
for (int k = 3; k k) {
//i表示子字符串中起始的位置
for (int i = 0; i ) {
//获取子字符串结束的位置，
int j = i + k - 1;
if (s.charAt(i) == s.charAt(j) && table[i+1][j-1]) {
table[i][j] = true;
if (k > maxLength) {
maxLength = k;
start = i;
}
}
}
}
return s.substring(start, start+maxLength);
}
}
方法3：分奇偶中心讨论
public class LongestPalindrome {
public static String longestPalSubstr(String s){
//最后字符串的长度
int maxLength = 1;
int start = 0;
int len = s.length();
int low ,hight;
//这里面用i表示中心点的位置
for (int i = 0; i ) {
//首先查找最长的偶数回文字符串,有两个中心点，分别为 i -1、 i
low = i -1;
hight = i;
while (low >= 0 && hight s.charAt(hight)) {
if (hight - low + 1 > maxLength) {
maxLength = hight - len + 1;
start = low;
}
--low;
++hight;
}
//其次寻找最长的奇数的最长回文字符串，中心点以i为主
low = i - 1;
hight = i + 1;
while (low >= 0 && hight s.charAt(hight)) {
if (hight - low + 1 > maxLength) {
maxLength = hight - low + 1;
start = low;
}
--low;
++hight;
}
}
//起始和结束的位置
return s.substring(start, start + maxLength);
}
}