把一個(gè)字符串劃分成幾個(gè)回文子串，枚舉所有可能的劃分
例如
For example, given?
s
?=?
"aab"
,
Return
[ ["aa","b"], ["a","a","b"] ]
寫一個(gè)子函數(shù)判斷是否為回文。
然后dfs，這個(gè)dfs比之前的稍微難理解一些。dfs函數(shù)每次輸入的起點(diǎn)代表之前已經(jīng)處理好了，從這個(gè)起點(diǎn)開始到結(jié)尾len的有幾種長(zhǎng)度可能組成，回文的都要dfs遍歷一次，如果沒有就++。例如輸入為abcc，假設(shè)此時(shí)start指向b了，那么b是回文，要dfs從start+1開始，因?yàn)閎的長(zhǎng)度為1，一直繼續(xù)。。。之后還要回到b開始長(zhǎng)度為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;
}
};
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
