当前位置 博文首页 > 数据结构和算法：LeetCode 647. 回文子串
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
if (s.charAt(i) != s.charAt(j))
continue;
dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
代码我们大致也能写出来了，因为是从i到j，所以j不能小于i。
for (int i = 0; i < length; i--) {
for (int j = i; j < length; j++) {
if (s.charAt(i) != s.charAt(j))
continue;
dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
}
}
但是这里有个问题，如果我们想要求dp[i][j]还需要知道dp[i+1][j-1]，如下图所示
对于这个二维数组，如果从上往下遍历当计算dp[i][j]的时候，我们还没有计算dp[i+1][j-1]的值，所以这个时候是没法计算dp[i][j]的，但我们可以从下往上计算，如下所示
//从下往上计算
for (int i = length - 1; i >= 0; i--) {
for (int j = i; j < length; j++) {
if (s.charAt(i) != s.charAt(j))
continue;
dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
}
}
我们来看下最终代码
public int countSubstrings(String s) {
int length = s.length();
boolean[][] dp = new boolean[length][length];
int count = 0;//回文串的数量
//字符串从后往前判断
for (int i = length - 1; i >= 0; i--) {
for (int j = i; j < length; j++) {
//如果i和j指向的字符不一样，那么dp[i][j]就
//不能构成回文字符串
if (s.charAt(i) != s.charAt(j))
continue;
dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
//如果从i到j能构成回文串，count就加1
if (dp[i][j])
count++;
}
}
return count;
}
public int countSubstrings(String s) {
int length = s.length();
boolean[][] dp = new boolean[length][length];
int count = 0;//回文串的数量
for (int j = 0; j < length; j++) {
for (int i = 0; i <= j; i++) {
//如果i和j指向的字符不一样，那么dp[i][j]就
//不能构成回文字符串
if (s.charAt(i) != s.charAt(j))
continue;
dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
//如果从i到j能构成回文串，count就加1
if (dp[i][j])
count++;
}
}
return count;
}
上面代码中dp是二维数组，但实际上在计算当前列的时候（如上图所示），我们只会用到上一列的结果，再往之前的就用不到了，所以我们还可以在优化一下，把二维数组改为一维。
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;
}
视频链接
//回文串的数量
int count = 0;
public int countSubstrings(String s) {
//边界条件判断
if (s == null || s.length() == 0)
return 0;
for (int i = 0; i < s.length(); i++) {
//回文的长度是奇数
extendPalindrome(s, i, i);
//回文是长度是偶数
extendPalindrome(s, i, i + 1);
}
return count;
}
//以left和right为中心点，求回文字符串的数量
private void extendPalindrome(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left--) == s.charAt(right++)) {
count++;
}
}
//中心点的个数
public int countSubstrings(String s) {
//字符串的长度
int length = s.length();
//中心点的个数
int size = 2 * length - 1;
//回文串的个数
int count = 0;
for (int i = 0; i < size; ++i) {
//要么left等于right，要么left+1等于right。也就是说如果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;
}
