Palindrome Partitioning

  • tags: [palindrome]

Question

  1. Given a string s, partition s such that every substring of the partition is a palindrome.
  3. Return all possible palindrome partitioning of s.
  5. For example, given s = "aab",
  6. Return
  8.   [
  9.     ["aa","b"],
  10.     ["a","a","b"]
  11.   ]

题解1 - DFS

罗列所有可能，典型的 DFS. 此题要求所有可能的回文子串，即需要找出所有可能的分割，使得分割后的子串都为回文。凭借高中的排列组合知识可知这可以用『隔板法』来解决，具体就是在字符串的每个间隙为一个隔板，对于长度为 n 的字符串，共有 n-1 个隔板可用，每个隔板位置可以选择放或者不放，总共有 O(2^{n-1}) 种可能。由于需要满足『回文』条件，故实际上需要穷举的状态数小于 O(2^{n-1}).

回溯法看似不难，但是要活学活用起来还是不容易的，核心抓住两点：深搜的递归建立和剪枝函数的处理。

根据『隔板法』的思想，我们首先从第一个隔板开始挨个往后取，若取到的子串不是回文则立即取下一个隔板，直到取到最后一个隔板。若取到的子串是回文，则将当前子串加入临时列表中，接着从当前隔板处字符开始递归调用回溯函数，直至取到最后一个隔板，最后将临时列表中的子串加入到最终返回结果中。接下来则将临时列表中的结果一一移除，这个过程和 subsets 模板很像，代码比这个文字描述更为清晰。

Python

  1. class Solution:
  2.     # @param s, a string
  3.     # @return a list of lists of string
  4.     def partition(self, s):
  5.         result = []
  6.         if not s:
  7.             return result
  9.         palindromes = []
  10.         self.dfs(s, 0, palindromes, result)
  11.         return result
  13.     def dfs(self, s, pos, palindromes, ret):
  14.         if pos == len(s):
  15.             ret.append([] + palindromes)
  16.             return
  18.         for i in xrange(pos + 1, len(s) + 1):
  19.             if not self.isPalindrome(s[pos:i]):
  20.                 continue
  22.             palindromes.append(s[pos:i])
  23.             self.dfs(s, i, palindromes, ret)
  24.             palindromes.pop()
  26.     def isPalindrome(self, s):
  27.         if not s:
  28.             return False
  29.         # reverse compare
  30.         return s == s[::-1]

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param s: A string
  5.      * @return: A list of lists of string
  6.      */
  7.     vector<vector<string>> partition(string s) {
  8.         vector<vector<string> > result;
  9.         if (s.empty()) return result;
  11.         vector<string> palindromes;
  12.         dfs(s, 0, palindromes, result);
  14.         return result;
  15.     }
  17. private:
  18.     void dfs(string s, int pos, vector<string> &palindromes, 
  19.              vector<vector<string> > &ret) {
  21.         if (pos == s.size()) {
  22.             ret.push_back(palindromes);
  23.             return;
  24.         }
  26.         for (int i = pos + 1; i <= s.size(); ++i) {
  27.             string substr = s.substr(pos, i - pos);
  28.             if (!isPalindrome(substr)) {
  29.                 continue;
  30.             }
  32.             palindromes.push_back(substr);
  33.             dfs(s, i, palindromes, ret);
  34.             palindromes.pop_back();
  35.         }
  36.     }
  38.     bool isPalindrome(string s) {
  39.         if (s.empty()) return false;
  41.         int n = s.size();
  42.         for (int i = 0; i < n; ++i) {
  43.             if (s[i] != s[n - i - 1]) return false;
  44.         }
  46.         return true;
  47.     }
  48. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param s: A string
  4.      * @return: A list of lists of string
  5.      */
  6.     public List<List<String>> partition(String s) {
  7.         List<List<String>> result = new ArrayList<List<String>>();
  8.         if (s == null || s.isEmpty()) return result;
  10.         List<String> palindromes = new ArrayList<String>();
  11.         dfs(s, 0, palindromes, result);
  13.         return result;
  14.     }
  16.     private void dfs(String s, int pos, List<String> palindromes, 
  17.                      List<List<String>> ret) {
  19.         if (pos == s.length()) {
  20.             ret.add(new ArrayList<String>(palindromes));
  21.             return;
  22.         }
  24.         for (int i = pos + 1; i <= s.length(); i++) {
  25.             String substr = s.substring(pos, i);
  26.             if (!isPalindrome(substr)) {
  27.                 continue;
  28.             }
  30.             palindromes.add(substr);
  31.             dfs(s, i, palindromes, ret);
  32.             palindromes.remove(palindromes.size() - 1);
  33.         }
  34.     }
  36.     private boolean isPalindrome(String s) {
  37.         if (s == null || s.isEmpty()) return false;
  39.         int n = s.length();
  40.         for (int i = 0; i < n; i++) {
  41.             if (s.charAt(i) != s.charAt(n - i - 1)) return false;
  42.         }
  44.         return true;
  45.     }
  46. }

源码分析

回文的判断采用了简化的版本，没有考虑空格等非字母数字字符要求。Java 中 ArrayList 和 List 的实例化需要注意下。Python 中 result 的初始化为[], 不需要初始化为 [[]] 画蛇添足。C++ 中的.substr(pos, n) 含义为从索引为 pos 的位置往后取 n 个(含) 字符，注意与 Java 中区别开来。

复杂度分析

DFS，状态数最多 O(2^{n-1}), 故时间复杂度为 O(2^n), 使用了临时列表，空间复杂度为 O(n).

Reference