647. 回文子串
原题链接:
https://leetcode.cn/problems/palindromic-substrings/description/
完成情况:
解题思路:
_647回文子串_dp法
这段代码是一个用于计算给定字符串中回文子串数量的解决方案。代码中定义了一个Solution类,其中包含一个countSubstrings方法,该方法接收一个字符串s作为参数,并返回回文子串的数量。
代码首先将输入字符串s转换为字符数组chars,并获取字符串长度len。然后创建一个二维布尔数组dp,用于记录字符串中各个子串是否为回文串。接着初始化一个变量result用于存储回文子串的数量。
代码使用动态规划的思想,在双重循环中遍历字符串中所有可能的子串。对于每个子串,检查其首尾字符是否相同,如果相同则根据不同情况更新result和dp数组:
- 情况一:子串长度为1,直接将回文子串数量加一,并标记dp[i][j]为true。
- 情况二:子串长度为2,同样将回文子串数量加一,并标记dp[i][j]为true。
- 情况三:子串长度大于2,且去掉首尾字符后的子串为回文串,也将回文子串数量加一,并标记dp[i][j]为true。
最终返回result作为回文子串的总数量。
_647回文子串_简易dp法
这段代码实现了一个计算给定字符串中回文子串数量的功能。以下是代码的解释:
- 定义了一个Solution类,其中包含一个公共方法countSubstrings,该方法接受一个字符串s作为参数,并返回回文子串的数量。
- 创建了一个二维布尔数组dp,用于记录字符串s中的回文子串。
- 初始化变量res为0,用于存储回文子串的数量。
- 使用两层循环遍历字符串s的所有可能子串,从后往前遍历i,从i到字符串末尾遍历j。
- 在每一对(i, j)中,如果s的第i个字符等于第j个字符,并且(j - i <= 1)或者子串s[i+1:j-1]也是回文串(即dp[i+1][j-1]为真),则将res加一,并将dp[i][j]标记为真。
- 最后返回res,即字符串s中回文子串的数量。
这段代码通过动态规划的方法计算字符串中的回文子串数量,时间复杂度为 O ( n 2 ) O(n^2) O(n2),其中n为字符串s的长度。
_647回文子串_中心扩展法
这段代码是一个Java解决方案类,其中的方法countSubstrings
用于计算给定字符串s
中的回文子串数量。
- 首先,代码会检查输入字符串
s
是否为空或长度小于1,若是则直接返回0。 - 然后,通过遍历字符串
s
的所有可能中心点(总共有 2 × len − 1 2 \times \text{len} - 1 2×len−1个中心点),向两边扩散来判断是否是回文子串。 - 对于每个中心点,有两种情况:一种是
left == right
,另一种是right = left + 1
,这两种情况的回文中心不同。 - 在扩散过程中,如果发现当前子串是回文串,则记录数量
ans
并继续向两边扩散。 - 最终返回回文子串的数量
ans
。
这段代码利用中心扩散法来快速计算回文子串的数量,通过遍历所有可能的中心点,从中心向两边扩散,判断是否是回文串。
_647回文子串_Manacher算法
这段代码是一个解决回文子串数量问题的算法。下面是对代码的清晰、简洁和易读的解释:
- 首先,将输入字符串 s s s进行预处理,构建一个新的字符串 t t t。在 t t t的开头插入字符’KaTeX parse error: Expected 'EOF', got '#' at position 4: '和'#̲',在sKaTeX parse error: Expected 'EOF', got '#' at position 11: 的每个字符后面插入'#̲',并在t$的末尾插入字符’!'。
- 初始化一个长度为 n n n的数组 f f f,以及三个变量 i M a x iMax iMax、 r M a x rMax rMax和 a n s ans ans,分别用来记录当前回文子串的中心、右边界和回文子串数量。
- 从索引1开始遍历字符串 t t t,对于每个位置 i i i:
- 计算 f [ i ] f[i] f[i]的初始值,如果 i i i在 r M a x rMax rMax的范围内,则 f [ i ] f[i] f[i]取 i i i关于 i M a x iMax iMax对称位置和 r M a x − i rMax-i rMax−i的较小值,否则 f [ i ] = 1 f[i]=1 f[i]=1。
- 从当前位置 i i i向两边进行中心拓展,直到不再是回文串为止,更新 f [ i ] f[i] f[i]的值。
- 动态更新 i M a x iMax iMax和 r M a x rMax rMax,确保包含当前最右边界的最大回文子串。
- 统计回文子串数量,贡献为 ( f [ i ] − 1 ) / 2 (f[i]-1)/2 (f[i]−1)/2的上取整值。
- 返回最终的回文子串数量 a n s ans ans。
整体来说,这段代码利用了中心拓展法来统计给定字符串中的回文子串数量。
参考代码:
_647回文子串_dp法
package 代码随想录.动态规划;
public class _647回文子串_dp法 {
/**
*
* @param s
* @return
*/
public int countSubstrings(String s) {
// 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
// 按下标为唯一标识符,不考虑字符的重复性,同时要保证是连续的。
char[] chars = s.toCharArray();
int len_chars = chars.length;
boolean [][] dp = new boolean[len_chars][len_chars];
int result = 0;
for (int i = len_chars - 1;i>=0;i--){
for (int j = i;j<len_chars;j++){
if (chars[i] == chars[j]){
if (j - i<=1){
result++;
dp[i][j] = true;
}else if (dp[i+1][j-1]){
result++;
dp[i][j] = true;
}
}
}
}
return result;
}
}
_647回文子串_简易dp法
package 代码随想录.动态规划;
public class _647回文子串_简易dp法 {
/**
*
* @param s
* @return
*/
public int countSubstrings(String s) {
// 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
// 按下标为唯一标识符,不考虑字符的重复性,同时要保证是连续的。
char[] chars = s.toCharArray();
int len_chars = chars.length;
boolean [][] dp = new boolean[len_chars][len_chars];
//也可以直接调s.length(),s.chatAt(i)方法直接获取。
int res = 0;
for (int i = s.length() - 1;i>=0;i--){
for (int j = i;j<s.length();j++){
if (s.charAt(i) == s.charAt(j) && (j-i <= 1 || dp[i+1][j-1])){
res++;
dp[i][j] = true;
}
}
}
return res;
}
}
_647回文子串_中心扩展法
package 代码随想录.动态规划;
public class _647回文子串_中心扩展法 {
/**
*
* @param s
* @return
*/
public int countSubstrings(String s) {
// 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
// 按下标为唯一标识符,不考虑字符的重复性,同时要保证是连续的。
int len_s = s.length(),res = 0;
if (s == null || len_s < 1 ){
return 0;
}
//总共有【2 * len - 1】个中心店
for (int i = 0; i < 2 * len_s - 1; i++){
//通过遍历每个回文中心,向两边扩散,并判断为是否回文字串
//有两种情况,left == right ,,, right = left + 1 ,,,这两种回文中心是不一样的。
int left = i/2,right = left + i % 2;
while (left >= 0 && right < len_s && s.charAt(left) == s.charAt(right)){
//如果当前是一个回文串,则记录效量
res++;
left--;
right++;
}
}
return res;
}
}
_647回文子串_Manacher算法
package 代码随想录.动态规划;
public class _647回文子串_Manacher算法 {
/**
*
* @param s
* @return
*/
public int countSubstrings(String s) {
// 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
// 按下标为唯一标识符,不考虑字符的重复性,同时要保证是连续的。
int len_s = s.length();
StringBuilder sb_s = new StringBuilder("s#");
for (int i = 0; i < len_s; i++) {
sb_s.append(s.charAt(i));
sb_s.append("#");
}
int len_sb_s = sb_s.length();
sb_s.append('!');
int [] dp = new int [len_sb_s];
int iMax = 0,rMax = 0,res = 0;
for (int i = 1;i<len_sb_s;i++){
//初始化 f[i]
dp[i] = i <= rMax ? Math.min(rMax - i + 1,dp[2*iMax - i]) : 1;
//中心扩展
while (sb_s.charAt(i + dp[i]) == sb_s.charAt(i - dp[i])){
++dp[i];
}
//动态维护iMax 和 rMax
if (i + dp[i] - 1 > rMax){
iMax = i;
rMax = i + dp[i] - 1;
}
//统计答案,当前贡献为(f[i] - 1)/2 向上取整
res += dp[i] / 2;
}
return res;
}
}