131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Solution

Approach 1: Recursion.

Approach 2: DP.

Code (Python)

Approach 1:

class Solution:
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        memory = {}
        return self._partition(s, memory)
    
    def _partition(self, s, memory):
        if len(s) == 1:
            return [[s]]
        if s in memory:
            return memory[s]
        result = []
        for i in range(1, len(s)):
            if self._is_palindrome(s[:i]):
                for part in self._partition(s[i:], memory):
                    result.append([s[:i]] + part)
        if self._is_palindrome(s):
            result.append([s])
        memory[s] = result
        return result
    
    # can also do a O(N^2) prescan to look for palindromes (with dynamic programming and a 2D table)
    def _is_palindrome(self, s):
        return s[::-1] == s

Approach 2:

Code (C++)

Approach 1:

// Recursion.
class Solution {
private:
    vector<vector<string>> res;
    bool isPalindrome(string s) {
        int head = 0;
        int tail = s.size() - 1;
        while (head < tail)
        {
            if (s[head] != s[tail])
                return false;
            head++;
            tail--;
        }
        return true;
    }
    void doPartition(string s, vector<string>& buf) {
        if (s.size() == 0)
        {
            res.push_back(buf);
            return;
        }
        for (int len = 1; len <= s.size(); ++len)
        {
            string curr = s.substr(0, len);
            if (!isPalindrome(curr))
                continue;
            buf.push_back(curr);
            doPartition(s.substr(len, s.size() - len), buf);
            buf.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        vector<string> buf;
        doPartition(s, buf);
        return res;
    }
};

Approach 2:

class Solution {
private:
    unordered_map<int,vector<vector<string>>> memo;
    bool isPalindrome(string s) {
        int head = 0;
        int tail = s.size() - 1;
        while (head < tail)
        {
            if (s[head] != s[tail])
                return false;
            head++;
            tail--;
        }
        return true;
    }
    vector<vector<string>> doPartition(string s, int head) {
        vector<vector<string>> res;
        if (head == s.size()) {
            res.push_back(vector<string>());
            return res;
        }
        if (memo.find(head) != memo.end())
            return memo[head];
        for (int i = head; i < s.size(); ++i) {
            string curr = s.substr(head, i - head + 1);
            if (!isPalindrome(curr))
                continue;
            vector<vector<string>> buf = doPartition(s, i + 1);
            for (int i = 0; i < buf.size(); ++i) {
                buf[i].insert(buf[i].begin(), curr);
                res.push_back(buf[i]);
            }
        }
        memo[head] = res;
        return res;
    }
public:
    vector<vector<string>> partition(string s) {
        return doPartition(s, 0);
    }
};

// DP.
class Solution {
private:
    bool isPalindrome(string s) {
        int head = 0;
        int tail = s.size() - 1;
        while (head < tail)
        {
            if (s[head] != s[tail])
                return false;
            head++;
            tail--;
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        int sSize = s.size();
        if (sSize == 0)
            return res;
        vector<vector<string>> memo[sSize+1] = {vector<vector<string>>(1, vector<string>())};
        for (int i = 1; i <= sSize; ++i)
        {
            for (int j = 1; j <= i; ++j)
            {
                string curr = s.substr(j - 1, i - j + 1);
                if (!isPalindrome(curr))
                    continue;
                vector<vector<string>> newSet = memo[j-1];
                for (int k = 0; k < newSet.size(); ++k)
                {
                    newSet[k].push_back(curr);
                    memo[i].push_back(newSet[k]);
                }
            }
        }
        return memo[sSize];
    }
};