C++ Bottom Up DP soln with explanation


  • 0
    N
    class Solution {
    public:
        int countSubstrings(string s) {
            // cache to store start index of first char of the palindrome
            // value as list of all end indeices of palindromes
            unordered_map<int,vector<int>> dp;
            int result = 0;
            if(s.empty())
                return result;
            //base case for the last char
            dp[s.size()-1] = vector<int>{s.size()-1};
            ++result;// single character itself is palindrome
            
            for(int left = s.size()-2;left>=0;--left){
                dp[left] = vector<int>{left};
                ++result; // single character itself is palindrome
                for(int end:dp[left+1]){
                    if((end == left + 1) && s[end] == s[left]){ // check if this and next char are same
                        dp[left].push_back(end);
                        ++result;
                    }
                    
                    if(end+1 < s.size() && s[end+1] == s[left]){
                        dp[left].push_back(end+1);
                        ++result;
                    }
                }
            }
            
            return result;
        }
    };
    

Log in to reply
 

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