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
