LeetCode 131 分割回文串
131.分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
暴力穷举的回溯
对于子串的划分，初始仅选取 cur 处的元素作为子串 str ，判断生成的子串是否是回文，若是回文则将子串加入到 tmp 数组中，cur+1 开始递归，在递归返回后，将 tmp 中的值pop完成回溯，在下一步循环中将 s[i] 加入到 str 中作为新的字串，再做判断和递归回溯。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
vector<string> tmp;
vector<vector<string>> res;
bool isSuit(string a){
for(int i=0;i<a.size()/2+1;i++){
if(a[i]!=a[a.size()-1-i]) return false;
}
return true;
}
void DFS(string s,int cur){
if(cur==s.size()){
res.push_back(tmp);
return;
}
string str;
for(int i=cur;i<s.size();i++){
str+=s[i];
if(isSuit(str)){
tmp.push_back(str);
DFS(s,i+1);
tmp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
DFS(s,0);
return res;
}
};
|
使用动态规划优化回文的判断
在回文的判断中，使用的是最简单的双指针移动的方式进行的。这样的判断是存在重复操作的。例如给定字符串”abcde”, 在已知”bcd”不是回文字串时, 不再需要去双指针操作”abcde”而可以直接判定它一定不是回文字串。（也就是对于字符串的中间不是回文，那么整体就一定不是回文）
判断回文的充分必要条件：给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是 s[0] == s[n-1] 且 s[1:n-1] 是回文字串。
此处使用一个二维数组 f[i][j] 表示字符串 s 中从 i 到 j 的子串是否是回文。那么首先是建立状态转移方程：
此处的状态转移方程：当 $i\ge j$ 时，>时不存在子串，=时为单个字符，所以必定为true。其他情况则是根据充要条件设置，两端满足并且中间满足。
那么要实现动态规划的过程：首先初始化处理的是 $i\ge j$ 的情形，将相应的元素置为true，然后对于 i 在计算时需要使用 i+1 的值，j 在计算时需要使用 j-1 的值。一个反向计算，一个正向计算。（并且此处是只需要计算 $i<j$ 的情形的。）
1
2
3
4
5
6
7
| vector<vector<bool>> res;
res.resize(s.size(),vector<bool>(s.size(),true));
for(int i=s.size()-1;i>-1;i--){
for(int j=i+1;j<s.size();j++){
res[i][j]=(s[i] == s[j]) && res[i + 1][j - 1];
}
}
|
在此基础上改经的结果为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
vector<string> tmp;
vector<vector<string>> res;
vector<vector<bool>> ispalindrome;
void DFS(string s,int cur){
if(cur>=s.size()){
res.push_back(tmp);
return;
}
for(int i=cur;i<s.size();i++){
if(ispalindrome[cur][i]){
tmp.push_back(s.substr(cur,i-cur+1));
DFS(s,i+1);
tmp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
int n=s.size();
ispalindrome.resize(n,vector<bool>(n,true));
for(int i=n-1;i>-1;i--)
for(int j=i+1;j<n;j++)
ispalindrome[i][j]=(s[i]==s[j])&&ispalindrome[i+1][j-1];
DFS(s,0);
return res;
}
};
|
将动态规划的数组改变为动态生成
也就是将动态规划的过程改为所谓的记忆化搜索。对于回文判断数组 ispalindrome 的值不进行预先生成，而是采用在判断的过程中进行生成，生成的方式与之前相同。 f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
private:
vector<vector<int>> f;
vector<vector<string>> ret;
vector<string> ans;
int n;
public:
void dfs(const string& s, int i) {
if (i == n) {
ret.push_back(ans);
return;
}
for (int j = i; j < n; ++j) {
if (isPalindrome(s, i, j) == 1) {
ans.push_back(s.substr(i, j - i + 1));
dfs(s, j + 1);
ans.pop_back();
}
}
}
int isPalindrome(const string& s, int i, int j) {
if (f[i][j]) {
return f[i][j];
}
if (i >= j) {
return f[i][j] = 1;
}
return f[i][j] = (s[i] == s[j] ? isPalindrome(s, i + 1, j - 1) : -1);
}
vector<vector<string>> partition(string s) {
n = s.size();
f.assign(n, vector<int>(n));
dfs(s, 0);
return ret;
}
};
|
小结
对于子串分割问题，本质上是在不断增长子串的长度，初始长度为1，然后向下递归，回溯后，将新的子串长度+1，再向下递归。