###### tags: `LeetCode` `DFS` `Medium` `String`
# LeetCode #131 [Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)
### (Medium)

給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正著讀和反著讀都一樣的字符串。

---

兩個重點:
1. 判斷字串是否為回文
2. 如何遍歷整個字串

判斷字串是否為回文的方法是將字串反轉, 然後比對反轉後的字串與原字串是否相等。

遍歷字串的方式:從長度1開始切割字串, 當切割的字串為回文時, 就將該回文字串存入暫存數組中, 並從下一個字元開始呼叫遞迴, 直到指標位置等於整個字串的長度, 此時將暫存數組存入答案數組中, 然後返回。而在整個迴圈遍歷完成後, 也需要返回。

需要注意的點是i的範圍從1到s.size()-pos。

---

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> tmp;
        vector<vector<string>> ans;
        dfs(0, tmp, ans, s);
        return ans;
    }
    bool check(string s){
        string tmp = s;
        reverse(tmp.begin(), tmp.end());
        if(tmp==s)return true;
        return false;
    }
    void dfs(int pos, vector<string>& tmp, vector<vector<string>>& ans, const string& s){
        if(pos==s.size()){
            ans.push_back(tmp);
            return;
        }
        for(int i=1;i<=s.length()-pos;i++){
            string subs = s.substr(pos, i);
            if(!check(subs))continue;
            tmp.push_back(subs);
            dfs(i+pos, tmp, ans, s);
            tmp.pop_back();
        }
        return;
    }
};