leetcode647. 回文子串-动态规划

leetcode647. 回文子串-动态规划

四月 11, 2020

leetcode647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:
输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.

示例 2:
输入: “aaa”
输出: 6
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

本题和leetcode5最长回文子串基本一样。
我的leetcode5题解
leetcode要求出最长的，这里只是符合回文就可以。
二维数组 dp[i][j] 表示 i~j 是不是回文子串。
判断当前状态是不是回文有两个条件：

  • 首字母和尾字母一样
  • i+1~j-1 也是回文的，并且存在 i+1~j-1 。也就是说去掉首尾字母还需要剩下字母，比如 “bb” 就需要特殊判断，单个字母也是，直接赋值为1.
    填表方式我在leetcode5题写过了，可以看上面，重要的是需要保证无后效性。

    准备工作结束，上代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public int countSubstrings(String s) {
           int n = s.length();
           int[][] dp = new int[n][n];
           int ans = 0;
           for (int i = n - 1; i >= 0; i--) {
               dp[i][i] = 1;
               ans ++;
               for (int j = n - 1; j > i; j--) {
                   if (s.charAt(i) == s.charAt(j) && i + 1 == j) {
                       dp[i][j] = 1;
                   }
                   if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] == 1) {
                       dp[i][j] = 1;
                   }
                   if (dp[i][j] == 1) {
                       ans ++;
                   }
               }
           }
           return ans;
       }
    leetcode76/100