131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

Problem

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

class Solution {
public:
    vector<vector<string>> partition(string &s) {
        vector<vector<string>> pars;
        vector<string> par;
        partition(s, pars, par, 0);
        return pars;
    }
    void partition(string &s, vector<vector<string>> &pars, vector<string> &par, int begin) {
        if (begin == s.size()) pars.emplace_back(par);
        for (int i = begin; i < s.size(); ++i) {
            if (!isPalindrome(s, begin, i)) continue;
            par.emplace_back(s.substr(begin, i - begin + 1));
            partition(s, pars, par, i + 1);
            par.pop_back();
        }
    }
    inline bool isPalindrome(string &s, int begin, int end) {
        do {
            if (s[begin] != s[end]) return false;
        } while (++begin <= --end);
        return true;
    }
};

• #backtracking