把一个字符串划分成几个回文子串，枚举所有可能的划分
例如
For example, given
s
=
"aab"
,
Return
[ ["aa","b"], ["a","a","b"] ]
写一个子函数判断是否为回文。
然后dfs，这个dfs比之前的稍微难理解一些。dfs函数每次输入的起点代表之前已经处理好了，从这个起点开始到结尾len的有几种长度可能组成，回文的都要dfs遍历一次，如果没有就++。例如输入为abcc，假设此时start指向b了，那么b是回文，要dfs从start+1开始，因为b的长度为1，一直继续。。。之后还要回到b开始长度为2的串也就是bc然后不是回文，再判断bcc不是回文。这里嵌套着的还是要好好理解。
class
Solution {
public
:
//
131
bool
isPalindrome131(
string
str)
{
int
len =
str.size();
if
(len <=
1
)
return
true
;
int
i =
0
;
while
(i <= len /
2
)
{
if
(str[i] != str[len - i -
1
])
return
false
;
i
++
;
}
return
true
;
}
void
dfs131(vector<vector<
string
> > &ans, vector<
string
> &tmp,
string
&s,
int
start)
{
int
len =
s.size();
if
(start >= len) {ans.push_back(tmp);
return
;}
for
(
int
i =
1
; i <= len - start; i++
)
if
(isPalindrome131(s.substr(start, i)))
{
tmp.push_back(s.substr(start, i));
dfs131(ans, tmp, s, start
+
i);
tmp.pop_back();
}
}
vector
<vector<
string
> > partition(
string
s)
{
int
len =
s.size();
vector
<vector<
string
> >
ans;
if
(len ==
0
)
return
ans;
vector
<
string
>
tmp;
dfs131(ans, tmp, s,
0
);
return
ans;
}
};
