131.Palindrome Partitioning

Tags: Medium Backtracking

Links: https://leetcode.com/problems/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"]
]

---

判断字符串可以分成回文子串的方法，或者换成计数也可以。很典型的DFS模型。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<string>> res;
        vector<string> tmp;
        DFS(s, 0, tmp, res);

        return res;
    }

    void DFS(const string & s, int pos, vector<string> & tmp, vector<vector<string>> & res)
    {
        if (pos == s.size()) { res.push_back(tmp); return; }

        for (int i = pos; i < s.size(); ++i) {
            if (!isPalindrome(s, pos, i)) continue;
            tmp.push_back(s.substr(pos, i - pos + 1));
            DFS(s, i + 1, tmp, res);
            tmp.pop_back();
        }
    }

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