class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];// 需要一个变量记录有多少个trueint result = 0;// 初始化 全为false，默认不是回文串
​for (int i = s.length()-1; i >= 0; i--) {for (int j = i; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)){// 两头相等也有一个字母"a"或者两个字母"aa"的情况，这也是回文串// 在两头相等的情况下，各往中间走一格是回文串他就是回文串// s.charAt(i+1)==s.charAt(j-1)不能直接比较字符相等 acefca就不是回文串if (j-i <= 1 || dp[i+1][j-1] == true) {dp[i][j] = true;result++;}}}
//            System.out.println(Arrays.toString(dp[i]));}return result;}
}

总结

本题有点难想到用二维的数组来记录是不是回文串，且需明确中间是回文两边才是回文，另一个就是我们的i是从从下往上遍历，这样的话每次判断回文才可以让i与j往中间走。

还有一种双指针的解法：

i与i+1中心扩散（i+2，i+3可由前面推导），判断两边是不是回文串

class Solution {public int countSubstrings(String s) {int reslut = 0;for (int i = 0; i < s.length(); i++) {// i-i 从 a 往两边扩散，判断多少个回文串reslut += extend(s,i,i,s.length());// i-i+1 从 aa 从两边扩散reslut += extend(s,i,i+1,s.length());}return reslut;}
​public int extend(String s, int i, int j, int len){int res = 0;while (i>=0 && ji--;j++;res++;}return res;}
}

最长回文子序列 LeetCode 516

题目链接：最长回文子序列 LeetCode 516 - 中等

思路

• dp[i] [j]：[i, j]的回文子序列的最长长度为dp[i] [j]

• 递推公式：

  • 相同if(s.charAt(i) == s.chatAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
  • 不同else dp[i][j] = max(dp[i][j-1] + dp[i+1][j]);

• 初始化：i和j相同的情况，即只有一个字母，就为回文串dp[i][i]=1

  • for(i = 0;i

• 遍历顺序：从下往上，从左到右

  for (i = s.length() - 1;i>=0;i--){for(int j = i+1;j

• 打印dp

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];// 初始化，i==j时，即一个字母的时候必为回文串for (int i = 0; i < s.length(); i++) {dp[i][i] = 1;}
​for (int i = s.length() - 1; i >= 0; i--) {for (int j = i+1; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)){// 两边的字母相等的情况，各往中间探一步，加上自己各一个dp[i][j] = dp[i+1][j-1] + 2;}else {// 不相等的情况，就i或j往中探一步dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}
//            System.out.println(Arrays.toString(dp[i]));}// 最右下角取结果相当于i=0的return dp[0][s.length()-1];}
}

Your input:"bbbab"
Output:4
Expected:4
stdout:[0, 0, 0, 0, 1][0, 0, 0, 1, 1][0, 0, 1, 1, 3][0, 1, 2, 2, 3][1, 2, 3, 3, 4]