[LeetCode] Palindrome Partitioning

The problem has a nice structure that backtracking naturally fits in. The structure is, given a starting position idx, we search from idx till the end of the string s.length() - 1. Once we reach a position i such that the sub-string from idx to i (s.substr(idx, i - idx + 1)) is a palindrome, we add it to a temporary tmp. Then we recursively call the same function to process the remaining sub-string. Once we reach the end of the string, we add tmp into the result res of all the possible partitioning.

Then, backtracking happens! Remember that at position i, we find s.substr(idx, i - idx + 1) to be a palindrome and we immediately add it to tmp. It is obvious that there may be some position j such that j > i and s.substr(idx, j - idx + 1) is also a palindrome. So we need to recover to the state before adding s.substr(idx, i - idx + 1) to tmp and continue to find the next palindrome position after i. And we simply need to pop s.substr(idx, i - idx + 1)out of tmp to make things work.

Putting these together, we can write down the following code, which should be self-explanatory.

 1 class Solution {
 2 public:
 3     vector<vector<string>> partition(string s) {
 4         vector<vector<string>> res;
 5         vector<string> tmp;
 6         getPartition(s, 0, tmp, res);
 7         return res;
 8     }
 9 private: 
10     void getPartition(string& s, int idx, vector<string>& tmp, vector<vector<string>>& res) {
11         if (idx == s.length()) {
12             res.push_back(tmp);
13             return;
14         }
15         for (int i = idx, n = s.length(); i < n; i++) {
16             int l = idx, r = i;
17             while (l < r && s[l] == s[r]) l++, r--;
18             if (l >= r) {
19                 tmp.push_back(s.substr(idx, i - idx + 1));
20                 getPartition(s, i + 1, tmp, res);
21                 tmp.pop_back();
22             }
23         }
24     }
25 };