LeetCode:Palindrome Partitioning
題目如下：（把一個字符串劃分成幾個回文子串，枚舉所有可能的劃分）
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"] ]
?
分析 ：首先對字符串的所有子串判斷是否是回文，設f[i][j] = true表示以i為起點，長度為j的子串是回文,等于false表示不是回文，那么求f[i][j]的動態規劃方程如下：
-
當j = 1，f[i][j] = true;
-
當j = 2，f[i][j] = (s[i]==s[i+1]),其中s是輸入字符串
-
當j > 2, f[i][j] = f[i+1][j-2] && (s[i] == s[i+j-1])（即判斷s[m..n]是否是回文時：只要s[m+1...n-1]是回文并且s[m] = s[n]，那么它就是回文，否則不是回文）
這一題也可以不用動態規劃來求f，可以用普通的判斷回文的方式判斷每個子串是否為回文。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 本文地址
求得f后，根據 f 可以構建一棵樹，可以通過DFS來枚舉所有的分割方式，代碼如下：
1
class
Solution {
2
public
:
3
vector<vector<
string
>> partition(
string
s) {
4
//
IMPORTANT: Please reset any member data you declared, as
5
//
the same Solution instance will be reused for each test case.
6
vector< vector<
string
> >
res;
7
int
len =
s.length();
8
if
(len ==
0
)
return
res;
9
//
f[i][j] = true表示以i為起點，長度為j的子串是回文
10
bool
**f =
new
bool
*
[len];
11
for
(
int
i =
0
; i < len; i++
)
12
{
13
f[i] =
new
bool
[len+
1
];
14
for
(
int
j =
0
; j < len+
1
; j++
)
15
f[i][j] =
0
;
16
f[i][
1
] =
true
;
17
}
18
for
(
int
k =
2
; k <= len; k++
)
19
{
20
for
(
int
i =
0
; i <= len-k; i++
)
21
{
22
if
(k ==
2
)f[i][
2
] = (s[i] == s[i+
1
]);
23
else
f[i][k] = f[i+
1
][k-
2
] && (s[i] == s[i+k-
1
]);
24
}
25
}
26
vector<
string
>
tmp;
27
DFSRecur(s, f,
0
, res, tmp);
28
for
(
int
i =
0
; i < len; i++
)
29
delete [](f[i]);
30
delete []f;
31
return
res;
32
}
33
34
void
DFSRecur(
const
string
&s,
bool
**f,
int
i,
35
vector< vector<
string
> > &res, vector<
string
> &
tmp)
36
{
//
i為遍歷的起點
37
int
len =
s.length();
38
if
(i >= len){res.push_back(tmp);
return
;}
39
for
(
int
k =
1
; k <= len - i; k++
)
40
if
(f[i][k] ==
true
)
41
{
42
tmp.push_back(s.substr(i, k));
43
DFSRecur(s, f, i+
k, res, tmp);
44
tmp.pop_back();
45
}
46
47
}
48
};
LeetCdoe:Palindrome Partitioning II
題目如下：（在上一題的基礎上，找出最小劃分次數）
Given a string? s , partition? s ?such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of? s .
For example, given?
s
?=?
"aab"
,
Return?
1
?since the palindrome partitioning?
["aa","b"]
?could be produced using 1 cut. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
本文地址
算法1 ：在上一題的基礎上，我們很容易想到的是在DFS時，求得樹的最小深度即可（遍歷時可以根據當前求得的深度進行剪枝），但是可能是遞歸層數太多，大數據時運行超時，也貼上代碼：
?
View Code
算法2 ：設f[i][j]是i為起點，長度為j的子串的最小分割次數，f[i][j] = 0時，該子串是回文，f的動態規劃方程是：
f[i][j] = min{f[i][k] + f[i+k][j-k] +1} ,其中 1<= k <j
這里f充當了兩個角色，一是記錄子串是否是回文，二是記錄子串的最小分割次數，可以結合上一題的動態規劃方程，算法復雜度是O(n^3), 還是大數據超時，代碼如下：
?
View Code
算法3 ：同上一題，用f來記錄子串是否是回文，另外優化最小分割次數的動態規劃方程如下,mins[i] 表示子串s[0...i]的最小分割次數：
- 如果s[0...i]是回文，mins[i] = 0
- 如果s[0...i]不是回文，mins[i] = min{mins[k] +1 (s[k+1...i]是回文) ?或 ?mins[k] + i-k ?(s[k+1...i]不是回文)} ，其中0<= k < i
代碼如下，大數據順利通過，結果Accept： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 本文地址
1
class
Solution {
2
public
:
3
int
minCut(
string
s) {
4
//
IMPORTANT: Please reset any member data you declared, as
5
//
the same Solution instance will be reused for each test case.
6
int
len =
s.length();
7
if
(len <=
1
)
return
0
;
8
//
f[i][j] = true表示以i為起點，長度為j的子串是回文
9
bool
**f =
new
bool
*
[len];
10
for
(
int
i =
0
; i < len; i++
)
11
{
12
f[i] =
new
bool
[len+
1
];
13
for
(
int
j =
0
; j < len+
1
; j++
)
14
f[i][j] =
false
;
15
f[i][
1
] =
true
;
16
}
17
int
mins[len];
//
mins[i]表示s[0...i]的最小分割次數
18
mins[
0
] =
0
;
19
for
(
int
k =
2
; k <= len; k++
)
20
{
21
for
(
int
i =
0
; i <= len-k; i++
)
22
{
23
if
(k ==
2
)f[i][
2
] = (s[i] == s[i+
1
]);
24
else
f[i][k] = f[i+
1
][k-
2
] && (s[i] == s[i+k-
1
]);
25
}
26
if
(f[
0
][k] ==
true
){mins[k-
1
] =
0
;
continue
;}
27
mins[k-
1
] = len -
1
;
28
for
(
int
i =
0
; i < k-
1
; i++
)
29
{
30
int
tmp;
31
if
(f[i+
1
][k-i-
1
] ==
true
)tmp = mins[i]+
1
;
32
else
tmp = mins[i]+k-i-
1
;
33
if
(mins[k-
1
] > tmp)mins[k-
1
] =
tmp;
34
}
35
}
36
for
(
int
i =
0
; i < len; i++
)
37
delete [](f[i]);
38
delete []f;
39
return
mins[len-
1
];
40
}
41
42
};
?【版權聲明】轉載請注明出處： http://www.cnblogs.com/TenosDoIt/p/3421283.html
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
