LeetCode 131. Palindrome Partitioning

华为云博客 技术博客 14683 31

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

[
  ["aa","b"],
  ["a","a","b"]
]
  • 1
  • 2
  • 3
  • 4

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

问题分析

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

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

Step 1 判断回文字符串

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

反转字符串法

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

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

双指针法

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

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

递归法

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

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; } }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

Step 2 拆分字符串

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

暴力回溯法

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

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

以题目中的aab为例：

实现代码如下：

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(); } } }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

递归法

递归法的思路是把一个字符串分为 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]

实现代码如下：

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;
}
  • 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

结果测试

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

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

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

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

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

文章来源: blog.csdn.net，作者：冰水比水冰，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/luoyhang003/article/details/72229094

（完）