Question

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

Return all possible palindrome partitioning of s.

Difficulty:Medium

Category:Backtracking

Analyze

Solution

class Solution {
 public:
  vector<vector<string>> partition(string s) {
    vector<string> out;
    vector<vector<string>> res;

    partitionDFS(s, 0, out, res);
    return res;
  }
  void partitionDFS(string s, int start, vector<string>& out, vector<vector<string>>& res) {
    if (start == s.size()) {
      res.emplace_back(out);
      return;
    }
    for (int i = start; i < s.size(); ++i) {
      if (isPalindrome(s, start, i)) {
        out.emplace_back(s.substr(start, i - start + 1));
        partitionDFS(s, i + 1, out, res);
        out.pop_back();
      }
    }
  }

  bool isPalindrome(string s, int left, int right) {
    while (left < right) {
      if (s[left++] != s[right--]) return false;
    }
    return true;
  }
};