0131. 分割回文串 [Medium] [Palindrome Partitioning].md

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"]
]

---

题目：通过合理的分隔，使得子串均为回文串。返回所有满足条件的分隔结果。

思路：回溯法，类似LeetCode93. Restore IP Addresses。每层递归处理一段子串，判断该段子串是否为回文。

工程代码下载

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> vec;
        if(s.empty())
            return res;
        helper(s, res, vec, 0);
        return res;
    }
private:
    void helper(const string s, vector<vector<string>>& res, vector<string>& vec, int start){
        if(start == s.size()){
            res.push_back(vec);
            return;
        }

        for(int i = start; i < s.size(); ++i){
            int len = i - start + 1;
            // 判断s[start..i]是否为回文串
            if(isPalindrome(s, start, start + len - 1)){
                vec.push_back(s.substr(start, len));
                helper(s, res, vec, i + 1);
                vec.pop_back();
            }
        }

        return;
    }

    bool isPalindrome(const string s, int l, int r){
        int k = l + (r - l) / 2;
        for(int i = l; i <= k; ++i){
            if(s[i] != s[r - (i-l)])
                return false;
        }
        return true;
    }
};