把一個字符串劃分成幾個回文子串，枚舉所有可能的劃分
例如
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;
}
};
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
