my c++ 14ms dp and backtracking solution


  • 1
    D

    The idea of this solution is simple. Record all palindromes of the string s in a 2d array, which will offer a constant look up time later in the recursion.

    class Solution {
    public:
        vector<vector<bool>> isPalin(string s) {
            vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), true));
            for(int i = s.size() - 1; i >= 0; i--) {
                for(int j = i + 1; j < s.size(); j++) {
                    if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                    else dp[i][j] = false;
                }
            }
            return dp;
        }
        void partition(vector<vector<string>>& result, vector<string>& ins, const vector<vector<bool>>& palin, const string& s, int idx) {  
            if(idx == s.size()) {                   //need to return
                result.push_back(ins);
                return;
            }
            for(int i = 1; i <= s.size() - idx; i++) {
                if(palin[idx][idx + i - 1]) {
                    ins.push_back(s.substr(idx, i));
                    partition(result, ins, palin, s, idx + i);
                    ins.pop_back();
                }
            }
        }
        vector<vector<string>> partition(string s) {
            vector<vector<bool>> palin = isPalin(s);
            vector<vector<string>> result;
            vector<string> ins;
            partition(result, ins, palin, s, 0);
            return result;
        }
    };
    

Log in to reply
 

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