LeetCode 131. Palindrome Partitioning

发表于 | 0 comments | 阅读次数

这篇文章是 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
2
3
4
[
  ["aa","b"],
  ["a","a","b"]
]

这道题的意思就是将给定的字符串分成回文串的组合，就像例子中所说，aab有两种回文串组合：aa,b和a,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。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！