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"]
]
Have you been asked this question in an interview?
这道题很值得推敲。首先给出先dp再dfs的方法，直接tls了，这里的dp比较粗暴，是计算字符串中所有字符是不是回文。估计这个地方消耗了很多时间，然后是dfs，dfs利用之前找到的dp数组，判断某段字符串是不是回文，然后形成了一颗dfs的树，在这些树里找问题的解。
这里总结下dfs：dfs其实是一种特殊的递归，只不过通常的递归是这样的：
fun(){
...
fun();
...
}
而dfs是这样的：
fun(){
...
for(int i=0;i
fun();
}
...
}
dfs每次运行到for的时候，它的解空间都分叉成n支，然后每一支又分叉成n支，这就形成了解空间的树。而dfs是深度优先访问这棵树的，这也是它的名字的由来。
通过dfs，我们考察了解的所有可能性，下面是code：
-
void dfs(string s, vector<string> &path, vector<vector<string>> &res)
-
{
-
if(s.size() < 1)
-
{
-
res.push_back(path);
-
return;
-
}
-
for(int i = 0; i < s.size(); i++)
-
{
-
int begin = 0;
-
int end = i;
-
while(begin < end)
-
{
-
if(s[begin] == s[end])
-
{
-
begin++;
-
end--;
-
}
-
else
-
break;
-
}
-
if(begin >= end)//bool isPalindrome = true;
-
{
-
path.push_back(s.substr(0,i+1));
-
dfs(s.substr(i+1),path,res);
-
path.pop_back();
-
}
-
}
-
}
-
vector<vector<string>> partition(string s) {
-
vector<vector<string>> res;
-
vector<string> path;
-
dfs(s,path,res);
-
return res;
-
}
阅读(750) | 评论(0) | 转发(0) |
