回文子串

计算这个字符串中有多少个回文子串

动态规划

1. 数组定义: 表示区间[i,j]的资产是否为回文子串, 如果是dp[i][j]则为true, 否为false
2. 递推: 整理来说就是两种, s[i]和s[j]相等或者不相等
   1. 相等有三种情况
      1. 下标i与j相同, 同一个字符例如a, b
      2. 下标差一位, 那就是aa, bb
      3. 下标相差大于一位, 比如cabac, 此时已经判断cc相等, 那么就继续判断aba是不是就行了, 所以就是判断i+1和j-1区间
3. 初始化: 一开始当然是false
4. 遍历顺序, 这里有点特殊, 根据递推公式可以看出来其遍历顺序是从下到上, 从左到右的

(i是竖的列, 这里可以用i--, 也可以先用j++算)

class Solution {public int countSubstrings(String s) {int len = s.length();boolean[][] dp = new boolean[len + 1][len + 1];//初始化是默认false, 所以不用动//直接开始遍历//这里没有再定义是i-1/j-1的数组了, 所以不用<=int result = 0;for(int j = 0; j < len; j++){for(int i = 0; i <= j; i++){//如果相等,而且相差<=2, 则直接加if(s.charAt(i) == s.charAt(j)){if(j - i <= 2){result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]){result++;dp[i][j] = true;}   //删除的情况就没要写了, 直接一边遍历一边判断}}}return result;}
}

双指针法:

确实回文串, 就是找中心然后向两边扩散看是不是对称的就可以了: 判断一个元素做中心点和两个元素做中心点的情况(正好对应情况1和情况2)

(就不细说了, 二刷再看)

class Solution {public int countSubstrings(String s) {int len, ans = 0;if (s == null || (len = s.length()) < 1) return 0;//总共有2 * len - 1个中心点for (int i = 0; i < 2 * len - 1; i++) {//通过遍历每个回文中心，向两边扩散，并判断是否回文字串//有两种情况，left == right，right = left + 1，这两种回文中心是不一样的int left = i / 2, right = left + i % 2;while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {//如果当前是一个回文串，则记录数量ans++;left--;right++;}}return ans;}
}

最长回文子序列

这里找的是最长的回文子序列长度, 子序列不是连续的

1. 数组: 字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]

2. 递推: 关键就是判断s[i]与s[j]是否相等, 相等则dp[i+1][j-1]+2(相当于往里走)

   如果不相等, 就max(dp[i-1][j], dp[i][j-1])

3. 初始化: 当dp[i][i]时, 就说明i和j相等时, 那么肯定是1, 比如a, b

4. 遍历顺序: 根据递推看出来也是左到右, 下到上, 从j开始就行(这里是有难度的)

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len + 1][len + 1];//先初始化, 都相同的字符串回文长度为1for(int i = 0; i < len; i++){dp[i][i] = 1;}//从后往前, 保证情况不漏for(int i = len - 1; i >= 0; i--){for(int j = i + 1; j < len; j++){//判断, 相等和不相等的情况if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i + 1][j - 1] + 2;} else {//不相等则分别改变dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][len - 1];}
}