# 131. Palindrome Partitioning 分割回文串

@TOC

## # 题目描述

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

## # 解题方法

### # 回溯法

``````class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
self.isPalindrome = lambda s : s == s[::-1]
res = []
self.helper(s, res, [])
return res

def helper(self, s, res, path):
if not s:
res.append(path)
return
for i in range(1, len(s) + 1): #注意起始和结束位置
if self.isPalindrome(s[:i]):
self.helper(s[i:], res, path + [s[:i]])
``````

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
helper(s, res, {});
return res;
}
void helper(string s, vector<vector<string>>& res, vector<string> path) {
if (s.size() == 0) {
res.push_back(path);
return;
}
for (int i = 1; i <= s.size(); i++) {
string pre = s.substr(0, i);
if (isPalindrome(pre)) {
path.push_back(pre);
helper(s.substr(i), res, path);
path.pop_back();
}
}
}
bool isPalindrome(string s) {
if (s.size() == 0) return true;
int start = 0, end = s.size() - 1;
while (start <= end) {
if (s[start] != s[end])
return false;
start ++;
end --;
}
return true;
}
};
``````

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
if (s.size() == 0) return res;
for (int i = 1; i <= s.size(); i++) {
string pre = s.substr(0, i);
if (isPalindrome(pre)) {
vector<vector<string>> next = partition(s.substr(i));
if (next.size() == 0)
next.push_back({""});
for (vector<string> vs : next) {
vector<string> path;
path.push_back(pre);
for (string s : vs) {
if (s == "")
continue;
path.push_back(s);
}
res.push_back(path);
}
}
}
return res;
}
bool isPalindrome(string s) {
if (s.size() == 0) return true;
int start = 0, end = s.size() - 1;
while (start <= end) {
if (s[start] != s[end])
return false;
start ++;
end --;
}
return true;
}
};
``````

## # 日期

2018 年 3 月 15 日 ——雾霾消散，春光明媚 2018 年 12 月 21 日 —— 一周就要过去了