# Leetcode 131:Palindrome Partitioning

Datetime:2016-08-23 01:21:31         Topic: LeetCode          Share        Original >>

Given a string s , partition  s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s .

For example, given s`"aab"` ,

Return

```[
["aa","b"],
["a","a","b"]
]```

Subscribe to see which companies asked this question

```//利用深度优先搜索DFS，将字符串划分为一组回文字符串
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
dfs(s, path, result, 0, 1);
return result;
}

//s[0,prev-1]之间已经处理，保证是回文串
//prev表示s[prev-1]与s[prev]之间的空隙位置，start同理
void dfs(string &s, vector<string>& path, vector<vector<string>>&result, int prev, int start)
{
if (start == s.size())
{ //最后一个隔板
if (ispalindrome(s, prev, start - 1))
{   //必须使用
path.push_back(s.substr(prev, start - prev));
result.push_back(path);
path.pop_back();
}
return;
}

//不断开
dfs(s, path, result, prev, start + 1);
//如果[prev,start-1]是回文，则可以断开，也可以不断开(上一行已经做了)
if (ispalindrome(s, prev, start - 1))
{
//断开
path.push_back(s.substr(prev, start - prev));
dfs(s, path, result, start, start + 1);
path.pop_back();
}
}

//判断子串是否为回文
bool ispalindrome(const string &s, int start, int end)
{
while (start < end && s[start] == s[end])
{
++start;
--end;
}
return start >= end;
}
};```