NC+LC：回文子串与最长回文子串
LC 647.回文子串
题目描述：
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 ：
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 ：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
解法一：中心扩散法
思路
- 遍历字符串，确定一个中心位置
- 回文长度为奇数时，左右指针指向同一个位置，为偶数以左右指针所指的两个元素为中心
- 找到中心后，往两边扩散，求回文子串的数量，当前位置的奇偶两种情况都需要考虑
实现代码
class Solution {
int count = 0;
public int countSubstrings(String s) {
if(s.length() == 0 || s == null){
return 0;
}
for (int i = 0; i < s.length(); i++) {
extendPalindrome(s, i, i); //回文的长度为奇数，left与right指向的中心为同一个位置
extendPalindrome(s, i, i + 1); //为偶数时，right指向left后一位
}
return count;
}
//以left和right为中心点，往两边扩散，求回文子串的数量
public void extendPalindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++)) {
count++;
}
}
}
优化
将求回文子串的方法放入循环中，注意中心点的个数为2*字符串长度-1，还有right的两种情况
class Solution {
public int countSubstrings(String s) {
if(s.length() == 0 || s == null){
return 0;
}
//字符串的长度
int length = s.length();
//中心点的个数，如aba->a,ab,b,ba,a有5个中心点
int size = 2 * length - 1;
//回文串的个数
int count = 0;
for (int i = 0; i < size; ++i) {
//right要么等于left，要么等于left+1
//如果left等于right，那么中心点就是一个字符，如果left+1等于right，中心点就是2个字符
int left = i / 2;
int right = left + i % 2;
while (left >= 0 && right < length && s.charAt(left--) == s.charAt(right++))
++count;
}
return count;
}
}
复杂度分析
-
时间复杂度：
。
-
空间复杂度：
。
解法二：动态规划
思路
- 定义二维数组dp，dp[l][r] 为 true，则表示字符串从 l 到 r 是回文子串
- r表示子串右边界，l表示子串左边界，当 s.charAt(l) != s.charAt(r) 则从 l 到 r 不可能构成回文子串
- 当 s.charAt(l) == s.charAt(r) 时，若该子串只有一个或两个字符，则为一个回文子串，如a，aa
-
当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 s.charAt(l) == s.charAt(r) 时，自然要看 dp[l+1][r-1] 是不是一个回文串。
实现代码
class Solution {
public int countSubstrings(String s) {
int len = s.length();
if(len == 0){
return 0;
}
boolean[][] dp = new boolean[len][len];
int count = 0;
for(int r = 0; r < len; r++){
for(int l = 0; l <= r; l++){
if(s.charAt(l) == s.charAt(r) && (r - l < 2 || dp[l+1][r-1])){
dp[l][r] = true;
count++;
}else{
dp[l][r] = false;
}
}
}
return count;
}
}
优化
用一维dp数组标记状态实现动态规划
class Solution {
public int countSubstrings(String s) {
int length = s.length();
boolean[] dp = new boolean[length];
int count = 0;
for (int j = 0; j < length; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1])) {
dp[i] = true;
count++;
} else {
dp[i] = false;
}
}
}
return count;
}
}
复杂度分析
-
时间复杂度：
NC17 + LC5：最长回文子串
题目地址：
解法一：暴力解法
优化：既然要取最长的，就从长到短判断其子串，遇到就直接截取返回，这样可大大减少时间，对于“cccccc...全是同一个元素组成的这种字符串，也能最早判断出来
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
for(int i = len; i > 0; i--){ //先确定末尾
for(int j = 0; j <= len-i; j++){
if(isPalindrome(s, j, j+i-1)){ //从长到短进行判断，是回文就直接截取返回
return s.substring(j, j + i);
}
}
}
return String.valueOf(s.charAt(0));
}
public boolean isPalindrome(String str, int left, int right){ //判断字符串是否是回文
while(left < right){
if(str.charAt(left++) != str.charAt(right--)){
return false;
}
}
return true;
}
}
复杂度分析
-
时间复杂度：
。
-
空间复杂度：
解法二：中心扩散法
思路
- 该解法是在题目647.回文子串解法的基础上改动得来，在进行中心扩散的过程中，不断截取当前的子串，比较长度，更新当前的最长回文子串
-
这种做法显然不是最好做法，每次扩散都需要截取，耗费时间
实现代码
class Solution {
public String longestPalindrome(String s) {
String res = "";
int len = s.length();
for(int i = 0; i < len*2-1; i++){
int left = i / 2;
int right = left + i % 2;
while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){
String pal = s.substring(left, right+1);
if(pal.length() > res.length()){
res = pal;
}
left--;
right++;
}
}
return res;
}
}
优化：通过start和end记录回文子串的开始和结束下标，最后再进行截取，这样大大降低了时间复杂度，推荐做法
class Solution {
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0; //标记最长回文子串的开头和结尾下标
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); //以i为中心进行扩散求回文子串长度
int len2 = expandAroundCenter(s, i, i + 1); //以i和i+1为中心
int len = Math.max(len1, len2);
if (len > end - start + 1) { //大于就根据长度和i更新start和end
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1); //根据start和end进行回文子串的截取
}
public static int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return right - left - 1;
}
}
解法三：动态规划
- 在LC 647.回文子串的动态规划解法的基础上进行修改
- 为回文子串就进行判断，更新当前回文子串的长度最大值以及记录该回文子串开始的位置
-
最后根据长度最大值以及开始位置截取字符串进行返回
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
boolean[][] dp = new boolean[len][len];
int start = 0; //最长回文子串的开始位置
int max = 1; //最长回文串的长度
for(int r = 0; r < len; r++){
for(int l = 0; l <= r; l++){
if(s.charAt(l) == s.charAt(r) && (r - l < 2 || dp[l+1][r-1])){ //是回文子串就标记并判断
dp[l][r] = true;
if((r - l + 1) > max){ //大于就更新位置与长度
start = l;
max = r - l + 1;
}
}else{
dp[l][r] = false;
}
}
}
return s.substring(start, start+max);
}
}
查看7道真题和解析