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:

1 2 3 4

[   ["aa","b"],   ["a","a","b"] ]

[
  ["aa","b"],
  ["a","a","b"]
]

Depth First Search Algorithm to Partition String into Palindromes

First we need to have a function to check if a given string (substring) is a palindrome, this should be fairly easy and can be done in O(N) time:

1
2
3
4
5
6
7
8
9
10

bool isPalindrome(const string &s) {
    int i = 0;
    int j = s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;            
        i ++;
        j --;
    }
    return true;
}

bool isPalindrome(const string &s) {
    int i = 0;
    int j = s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;            
        i ++;
        j --;
    }
    return true;
}

Then, we can perform a Depth First Search (DFS) algorithm to jump to next partition position (if current part is a palindrome). In this case, we backtrack (disregard the useless branches where current substring is not a palindrome).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<vector<string>> partition(string s) {
        dfs(s, {});
        return ans;
    }
    
private:
    vector<vector<string>> ans;
    void dfs(const string &s, vector<string> cur) {
        if (s.empty()) {
            ans.push_back(cur);
            return;
        }
        for (int i = 0; i < s.size(); ++ i) {
            string first = s.substr(0, i + 1);
            if (isPalindrome(first)) {
                cur.push_back(first);
                dfs(s.substr(i + 1), cur);
                cur.pop_back();
            }
        }
    }
};

class Solution {
public:
    vector<vector<string>> partition(string s) {
        dfs(s, {});
        return ans;
    }
    
private:
    vector<vector<string>> ans;
    void dfs(const string &s, vector<string> cur) {
        if (s.empty()) {
            ans.push_back(cur);
            return;
        }
        for (int i = 0; i < s.size(); ++ i) {
            string first = s.substr(0, i + 1);
            if (isPalindrome(first)) {
                cur.push_back(first);
                dfs(s.substr(i + 1), cur);
                cur.pop_back();
            }
        }
    }
};

When we reach the end of the string, we push the current partition solution to the array. The complexity will be O(2^N) in the worst case for strings like “aaaa…”. The overall complexity is O(N*2^N).

We may improve the solution by using Dynamic Programming to remember the isPalindrome value for substring[i..j]. Then the complexity will be O(2^N + N^2)

–EOF (The Ultimate Computing & Technology Blog) —