C++ clear DP solution


  • 0
    M
        int countSubstrings(string s) {
            if(s.size()==0) return 0;
            int res=0;
            vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
            dp[0][0]=2;
            for(int i=1;i<s.size();i++) {
                for(int j=0;j<i;j++) {
                    if(dp[i-1][j]==2&&s[i]==s[i-1]) dp[i][j+1]=2;
                    else if(dp[i-1][j]>0&&j!=i-1&&s[i-j-2]==s[i]) dp[i][j+2]=1;
                }
                dp[i][0]=2;
            }
            for(int i=0;i<dp.size();i++) {
                for(int j=0;j<dp[i].size();j++) res+=min(1, dp[i][j]);
            } 
            return res;
        }

  • 0

    Mind some explanation? Maybe what each entry stands for at least?

    I have suffered enough guessing somebody else's intention in a relationship, please make the coding world a little easier on me : )


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.