Best DFS solution in C++ yet using DP to accelerate from 12ms to 8ms


  • 1

    Here is the intuitive DFS solution:

    class Solution {
    private:
        int sLen;
        void search(const string& s, int pos, vector<string>& v, vector<vector<string>>& vv)
        {
            if(sLen == pos) vv.push_back(v);
            for(int i = pos; i < sLen; ++i)
            {
                int l = pos, r = i;
                while(l<r && s[l]==s[r]) l++, r--;
                if(l >= r) 
                {
                    string t = s.substr(pos, i-pos+1);
                    v.push_back(t);
                    search(s, i+1, v, vv);
                    v.pop_back();
                }
            }
        }
    public:
        vector<vector<string>> partition(string s) 
        {
            sLen = s.length();
            vector<string> v;
            vector<vector<string>> vv;
            search(s, 0, v, vv);
            return vv;
        }
    };
    

    Now let's take a look at its optimised version using DP to eliminate lots of redundant checking between index l and r.

    class Solution {
    private:
        int sLen;
        void search(string&s, int pos, bool** isPal, vector<string>& v, vector<vector<string>>& vv)
        {
            if(pos == sLen) { vv.push_back(v); return ; }
            for(int i = pos; i < sLen; ++i)
            {
                if(isPal[pos][i]) 
                {
                    v.push_back(s.substr(pos, i-pos+1));
                    search(s, i+1, isPal, v, vv);
                    v.pop_back();
                }
            }
        }
    public:
        vector<vector<string>> partition(string s) 
        {
            sLen = s.length();
            bool **isPal = (bool**)malloc(sizeof(bool*)*sLen);
            for(int i = 0; i < sLen; ++i)
            {
                isPal[i] = (bool*)malloc(sizeof(bool)*sLen);
                memset(isPal[i], 0, sizeof(bool)*sLen);
            }
            for(int i = sLen-1; i >= 0; --i)
            {
                for(int j = i; j < sLen; ++j)
                {
                    if(s[j]==s[i] && (j-i<2 || isPal[i+1][j-1]))
                        isPal[i][j] = true;
                }
            }
            vector<string> v;
            vector<vector<string>> vv;
            search(s, 0, isPal, v, vv);
            return vv;
        }
    };
    

Log in to reply
 

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