# 131. Palindrome Partitioning

## 1.問題 

* 給予一個字串, 分割為各種可能是回文的substring

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNV9Pk_AqTJTesdausi%2F-LNVBpEd-0LSdzvY-bgP%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-28%20%E4%B8%8B%E5%8D%888.40.49.png?alt=media\&token=de3447fb-1232-45a2-960d-bf006eb2f46e)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* function header, parameter
* test input
* 觀察
  * 其實可以看成排列組合, 上一回起始點為0, 終點為n, 下一回合的起始點n + 1, 終點為m, 當m + 1為string.length時return&#x20;
  * substr的用法
* 說明想法
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res; 
        vector<string> record;
        getSubStr(res, record, s, 0);
        return res;
    }
private:
    void getSubStr(vector<vector<string>>& res, vector<string>& record, string s, int start) {
        if (start == s.size()) {
            res.push_back(record);
            return; 
        }
        
        for (int i = start; i < s.size(); i++) {
            //substr的長度參數要算入自己
            int len = i - start + 1;
            string tmp = s.substr(start, len); 
            if (isPalindrome(tmp)) {
                record.push_back(tmp);
                getSubStr(res, record, s, i + 1); 
                record.pop_back();
            }
        }
    }
    
    bool isPalindrome(string s) {
        int size = s.length();
        for (int i = 0; i < size / 2; i++) {
            if (s[i] != s[size - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};
```