1、思路
以字符串google
为例,处理顺序如下:
-
当处理到第一个字符
g
时,此时包括字符g
在内后面一共有6个字符,面临6个选项,即可以分割出6个以字符g
开头的子字符串,分别为g
、go
、goo
、goog
、googl
、google
; -
对上面的每个子字符串做回文判断,只取回文的选项,然后进入下一层
dfs
。
2、代码
class Solution {
private:
vector<vector<string>> res;
vector<string> tmp;
public:
bool check(string& s, int st, int ed) //判断字符串是否回文
{
while (st < ed)
{
if (s[st ++ ] != s[ed -- ])
{
return false;
}
}
return true;
}
void dfs(string& s, int st)
{
if (st == s.length())
{
res.push_back(tmp);
return;
}
for (int i = st; i < s.length(); ++ i)
{
if (check(s, st, i) == true) //当前子字符串为回文,保存结果进入下一层dfs
{
tmp.push_back(s.substr(st, i - st + 1));
dfs(s, i + 1);
tmp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
dfs(s, 0);
return res;
}
};