首页 > 其他 > 详细

LeetCode 647. Palindromic Substrings

时间:2018-02-10 16:38:10      阅读:206      评论:0      收藏:0      [点我收藏+]

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:
The input string length won‘t exceed 1000.

分析

dp[i][j] 如果等于1就表示 string s 从下标i到j的那部分是 palindromic 的,而 string s 从 m 到 n 的部分只需要满足 s[m]==s[n] 并且 dp[m+1][n-1]==1 (即首尾相等,并且中间的是 palindromic )就是palindromic.

class Solution{
private:
    int dp[1000][1000];
public:
    int countSubstrings(string s) {
        for(int i=0;i<s.size();i++)
            dp[i][i]=1;
        int cnt=s.size();
        for(int len=2;len<=s.size();len++)
            for(int i=0;i<=s.size()-len;i++)
                if(len==2&&s[i]==s[i+1]){
                    dp[i][i+1]=1;
                    cnt++;
                }else if(s[i]==s[i+len-1]&&dp[i+1][i+len-2]==1){
                    dp[i][i+len-1]=1;
                    cnt++;
                }
        return cnt;
    }   
};

LeetCode 647. Palindromic Substrings

原文:https://www.cnblogs.com/A-Little-Nut/p/8439012.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!