Leetcode之动态规划（DP）专题-647. 回文子串（Palindromic Substrings）

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"

输出: 3

解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"

输出: 6

说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:

输入的字符串长度不会超过1000。

dp：

定义：dp[i][j]表示在从i开始到j结束这段字符串里，如果是回文串，则dp[i][j]=1，不是则dp[i][j]=0;

状态转移方程：

if((s.charAt(i)==s.charAt(j)) && ((j-i<=2) || dp[i+1][j-1]==1)){

　　dp[i][j] = 1;

}

举例解释：

"aba"

i=2 j=2　　　　"a" 长度为1，是回文字符串。

i=1 j=1　　　　"b" 长度为1，是回文字符串

i=1 j=2　　　　"ab" 长度为2，但左不等于右，不是

i=0 j=0　　　　"a" 长度为1，是回文字符串

i=0 j=1　　　　"ab" 长度为2，且左不等于右，不是

i=0 j=2　　　　"aba" 长度为3，且左等于右，是

　　　　　　　　（只要长度为3，且左等于右，不管中间是什么，都是回文字符串）

再举一种情况　　"abba"

i=0 j=3 截取后为"abba" 左等于右，但长度大于3，接着判断dp[i+1][j-1]是不是1，即判断dp[1][2]，即字符串"bb"是不是回文串。

class Solution {

    public int countSubstrings(String s) {

        int res = 0;

        int n = s.length();

        int[][] dp = new int[n][n];

        for (int i = n-1; i >= 0; i--) {

            for (int j = i; j < n; j++) {

                if((s.charAt(i)==s.charAt(j)) && ((j-i<=2) || dp[i+1][j-1]==1)){

                    dp[i][j] = 1;

                    res++;

                }

            }

        }

        return res;

    }

}

巴特西

Leetcode之动态规划（DP）专题-647. 回文子串（Palindromic Substrings）

最新文章

热门文章