LeetCode 131. Palindrome Partitioning

这篇文章是 LeetCode 131. 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

1
[
  ["aa","b"],
  ["a","a","b"]
]

这道题的意思就是将给定的字符串分成回文串的组合,就像例子中所说,aab有两种回文串组合:aa,ba,a,b.

问题分析

对于这个问题,我们很简单的将它分解为两个子问题:

  • 拆分字符串
  • 判断一个字符串是否是回文串

Step 1 判断回文字符串

如果一个字符串正读和反读结果都一样,我们就说它是一个回文字符串。判断一个字符串是不是回文的有很多种方法,我想起来 3 种方法,都会在接下来的文章中进行介绍,并给出源码(文中的代码皆为 C++)。

反转字符串法

这个方法是最容易理解的,将字符串反转,如果和原来的字符串一样,那么它就是回文的,这个方法在编码上也是最简单的:

1
2
3
4
5
6
7
8
bool isPalindrome_reverse(string s, int i, int j){
string r = s;
reverse(s.begin(),s.end());
if(s.compare(r)!=0){
return false;
}
return true;
}

双指针法

双指针法是通过两个指针,一个指向字符串首,另一个指向字符串尾,如果两个指针指向的字符相同,则两个指针向中间移动,继续判断。

1
2
3
4
5
6
7
8
9
10
bool isPalindrome_doublepoints(string s, int i, int j){
while(i < j){
if(s[i] != s[j]){
return false;
}
i++;
j--;
}
return true;
}

递归法

递归法和双指针法很类似,当前字符串是否回文取决于首尾字符是否相同,然后递归的判断除去首尾的剩余字符串是否回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isPalindrome_recursion(string s, int i,int j){
if(i == j){
return true;
}
else{
if(s[i] == s[j]){
i++;
j--;
if(i < j){
return isPalindrome_recursion(s, i, j);
}
else{
return true;
}
}
else{
return false;
}
}
}

Step 2 拆分字符串

这一步是这个问题的关键,解决拆分字符串的方案也有 2 种:暴力回溯法递归法

暴力回溯法

暴力回溯法比较好理解,它使用的是回溯法的思想,我们穷举出来字符串的所有子串组合,然后判断其中的子串是不是回文的,去掉不符合要求的组合,剩余的就是我们要的结果。

在进行穷举的时候,如果遇到不是回文的子串,我们就进行回溯。

以题目中的aab为例:

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void backtrace(vector<vector<string>> &vec, vector<string> &temp, string s, int start){
if(start == s.length()){
vec.push_back(temp);
}
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
temp.push_back(s.substr(start, i-start+1));
backtrace(vec, temp, s, i+1);
temp.pop_back();
}
}
}
}

递归法

递归法的思路是把一个字符串分为 A+B,如果 A 为回文则递归的求 B 的回文组合,然后将 A 和 B 的回文串组合做笛卡尔积。

以字符串 aabb 为例:

  1. 将aabb 分为 a+abb,然后求 abb 的回文组合为[a, b, b], [a, bb],所以做笛卡尔积后为:[a, a, b,b ], [a, a, bb]
  2. 将字符串分为 aa+bb,然后求 bb 的回文组合为[b, b], [bb],结果为[aa, b, b], [aa, bb]
  3. 将字符串分为 aab+b,aab 不回文
  4. aabb 回文,结果为[aabb]
  5. 最终结果为:[a, a, b,b ], [a, a, bb], [aa, b, b], [aa, bb], [aabb]

实现代码如下:

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
vector<vector<string>> partition_recursion(string s){
vector<vector<string>> vec;

if(s.length() == 0){
return vec;
}

if(isPalindrome_recursion(s, 0, s.length()-1)){
vector<string> temp;
temp.push_back(s);
vec.push_back(temp);
}

for(int i = 1; i <= s.length(); i++){
string left = s.substr(0, i);
if(isPalindrome(left, 0, left.length()-1)){
string right = s.substr(i, s.length()-i);
vector<vector<string>> rightVec = partition_recursion(right);
if(rightVec.size() > 0){
for(int j = 0; j < rightVec.size(); j++){
vector<string> temp;
temp.push_back(left);
for(int x = 0; x < rightVec[j].size(); x++){
temp.push_back(rightVec[j][x]);
}
vec.push_back(temp);
}
}
}
}
return vec;
}

结果测试

将几种方法组合后的测试结果如下:

反转字符串法 双指针法 递归法
暴力回溯法 16 ms 13 ms 13 ms
递归法 89 ms 76 ms 76 ms

我们看到回溯法要明显优于递归的方法。

本文的完整代码详见我的 GitHub


本文的版权归作者 罗远航 所有,采用 Attribution-NonCommercial 3.0 License。任何人可以进行转载、分享,但不可在未经允许的情况下用于商业用途;转载请注明出处。感谢配合!