C++ Backtrack with memoization.


  • 0
    H
    class Solution {
    public:
        using VVS = vector<vector<string>>;
        using VS = vector<string>;
        using VVB = vector<vector<bool>>;
        
        VVS partition(string s) {
            int len = s.size();
            VVS res;
            VS cur;
            VVB isPalindrome(len, vector<bool>(len, false));
            helper(s, 0, cur, isPalindrome, res);
            return res;
        }
        
        void helper(const string &s, int start, VS &cur, VVB &isPalindrome, VVS &res) {
            if (start == s.size()) {
                res.push_back(cur);
                return;
            }
            
            for (int i = start; i < s.size(); ++i) {
                if (i > start && (s[i] != s[start] || (i > start + 1 && !isPalindrome[start+1][i-1]))) continue;
                isPalindrome[start][i] = true;
                cur.push_back(s.substr(start, i-start+1));
                helper(s, i+1, cur, isPalindrome, res);
                cur.pop_back();
            }
        }
    };

Log in to reply
 

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