647.回文子串
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
示例 1:
输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c"
示例 2:
输入:"aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示:
输入的字符串长度不会超过 1000 。
参考思路
1. 定义状态
dp[i][j] 表示从位置 i 到 j 上的字符串是否为回文串,例如: i = 0, j = 1 表示字符串ab,则dp[0][1] = false
2. 状态转移(DP方程)
对于 i 到 j 上的位置的字符串,如果 s[i] == s[j] 且满足以下几点,则为回文串
- i 与 j 的距离 <= 2, 则为回文串。例如 aa 、aba 均为回文串
- i 与 j 的距离 > 2, 且 dp[i+1][j-1] == true, 则为回文串。例如 abccba, i+1 —> j-1 的字符串为 bccb,其为回文串
3. 定义边界
i 从字符串末尾依次向头移动,判断以 i 字符开头,以 s.length() - 1 结尾结束的字符串之间存在的回文串树,因此 j 每次从字符串尾开始移动,知道 i == j,结束一轮比较。
参考代码1
public int countSubstrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
// dp[i][j] 表示第i个字符到第j个字符是否为回文串
boolean[][] dp = new boolean[n][n];
int count = 0;
// 依次以i开头的字符串,判断从i j 之间是否有回文串
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = s.length() -1; j >= i; j--) {
// dp[i][j] = (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1]))
if (s.charAt(i) == s.charAt(j) && (j - i <=2 || dp[i+1][j-1])) {
dp[i][j] = true;
}
if (dp[i][j]) {
count++;
}
}
}
return count;
}
参考代码2
class Solution {
/**
* 1.定义子问题
* 字符串s[i...j]计算有多少个回文子串,可以分解成每个
* 2.定义状态
* 定义数组dp[i][j],表示字符串s[i...j]是否为回文字符串
* dp[i][j] = true,表示是回文子串
* dp[i][j] = false,表示不是回文子串
* 3.DP方程
* (1)如果s[i] == s[j],那么说明只要dp[i+1][j-1]是回文子串,那么dp[i][j]也就是回问子串
* (2)如果s[i] != s[j],那么说明dp[i][j]必定不是回文子串
*/
public int countSubstrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
boolean[][] dp = new boolean[n][n];
int result = n;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
// j 和 i相邻的时候
if (j - i == 1) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i+1][j-1];
}
} else {
dp[i][j] = false;
}
if (dp[i][j]) {
result++;
}
}
}
return result;
}
}
以上两个参考代码,时间复杂度:,空间复杂度:
参考代码3
降维,空间复杂度优化为
把上图的表格横向压扁,竖向一列看作一维数组,还是原来的扫描方向。一维表格中的格子在迭代中更新
class Solution {
public int countSubstrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
boolean[] dp = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
dp[i] = true;
count++;
for (int j = 0; j < i; j++) {
if (s.charAt(j) == s.charAt(i) && dp[j+1]) {
dp[j] = true;
count++;
} else {
dp[j] = false;
}
}
}
return count;
}
}
部分图片来源于网络,版权归原作者,侵删。
网友评论