<ul id="k6oey"></ul>

力扣(LeetCode)647

lemanli 發(fā)布于2019-08-19 11:34 / 2073人閱讀

摘要：示例輸入輸出解釋三個(gè)回文子串示例輸入輸出說(shuō)明個(gè)回文子串注意輸入的字符串長(zhǎng)度不會(huì)超過(guò)。解答這一題可以用窮舉法，檢查是否為回文字串但是應(yīng)該會(huì)超時(shí)。設(shè)置表示是否是回文字串，若是為，否則為。

題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一個(gè)字符串，你的任務(wù)是計(jì)算這個(gè)字符串中有多少個(gè)回文子串。

具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會(huì)被計(jì)為是不同的子串。

示例 1:

輸入: "abc"
輸出: 3
解釋: 三個(gè)回文子串: "a", "b", "c".
示例 2:

輸入: "aaa"
輸出: 6
說(shuō)明: 6個(gè)回文子串: "a", "a", "a", "aa", "aa", "aaa".
注意:

輸入的字符串長(zhǎng)度不會(huì)超過(guò)1000。

解答：
這一題可以用窮舉法，檢查s[i...j]是否為回文字串但是應(yīng)該會(huì)超時(shí)。
不過(guò)我們可以這么想，如果現(xiàn)在知道了s[i...j]是回文字串，那么如果
s[i-1] == s[j+1]，那么s[i-1...j+1]也一定是回文字串。這樣就聯(lián)想到了
動(dòng)態(tài)規(guī)劃。
設(shè)置dp[i] [j]表示s[i...j]是否是回文字串，若是為true，否則為false。
那么對(duì)任意的dp[i] [j] = dp[i+1] [j-1]&&s[i]==s[j]。一旦為true就把
結(jié)果+1。
不過(guò)需要注意的是要使用上述的遞推公式，需要先求出所有長(zhǎng)度為1和為2的回文字串，這個(gè)比較
簡(jiǎn)單，就不贅述了。
java ac代碼：

class Solution {
    public int countSubstrings(String s) {
        //dp[i][j]表示s[i...j]是否為回文字串。
        boolean[][] dp = new boolean[s.length()][s.length()];
        int ans = 0;
        for(int i = 0;i < dp.length;i++)
        {
            dp[i][i] = true;
            ans++;
        }
        for(int i = 1;i < dp.length;i++)
        if(s.charAt(i-1) == s.charAt(i))
        {
            dp[i-1][i] = true;
            ans++;
        }
        for(int k = 2;k < s.length();k++)
            for(int i = k;i < s.length();i++)
                if(s.charAt(i-k) == s.charAt(i)&&dp[i-k+1][i-1])
                {
                    dp[i-k][i] = true;
                    ans++;
                }
        return ans;
    }
}