# Palindrome Partitioning - tags: [palindrome] ### Source - leetcode: [Palindrome Partitioning | LeetCode OJ](https://leetcode.com/problems/palindrome-partitioning/) - lintcode: [(136) Palindrome Partitioning](http://www.lintcode.com/en/problem/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 - [DFS](# "Depth-First Search, 深度優先搜索") 羅列所有可能，典型的 [DFS](# "Depth-First Search, 深度優先搜索"). 此題要求所有可能的回文子串，即需要找出所有可能的分割，使得分割后的子串都為回文。憑借高中的排列組合知識可知這可以用『隔板法』來解決，具體就是在字符串的每個間隙為一個隔板，對于長度為 n 的字符串，共有 n-1 個隔板可用，每個隔板位置可以選擇放或者不放，總共有 O(2n?1)O(2^{n-1})O(2n?1) 種可能。由于需要滿足『回文』條件，故實際上需要窮舉的狀態數小于 O(2n?1)O(2^{n-1})O(2n?1). 回溯法看似不難，但是要活學活用起來還是不容易的，核心抓住兩點：**深搜的遞歸建立和剪枝函數的處理。** 根據『隔板法』的思想，我們首先從第一個隔板開始挨個往后取，若取到的子串不是回文則立即取下一個隔板，直到取到最后一個隔板。若取到的子串是回文，則將當前子串加入臨時列表中，接著從當前隔板處字符開始遞歸調用回溯函數，直至取到最后一個隔板，最后將臨時列表中的子串加入到最終返回結果中。接下來則將臨時列表中的結果一一移除，這個過程和 subsets 模板很像，代碼比這個文字描述更為清晰。 ### Python ~~~ class Solution: # @param s, a string # @return a list of lists of string def partition(self, s): result = [] if not s: return result palindromes = [] self.dfs(s, 0, palindromes, result) return result def dfs(self, s, pos, palindromes, ret): if pos == len(s): ret.append([] + palindromes) return for i in xrange(pos + 1, len(s) + 1): if not self.isPalindrome(s[pos:i]): continue palindromes.append(s[pos:i]) self.dfs(s, i, palindromes, ret) palindromes.pop() def isPalindrome(self, s): if not s: return False # reverse compare return s == s[::-1] ~~~ ### C++ ~~~ class Solution { public: /** * @param s: A string * @return: A list of lists of string */ vector<vector<string>> partition(string s) { vector<vector<string> > result; if (s.empty()) return result; vector<string> palindromes; dfs(s, 0, palindromes, result); return result; } private: void dfs(string s, int pos, vector<string> &palindromes, vector<vector<string> > &ret) { if (pos == s.size()) { ret.push_back(palindromes); return; } for (int i = pos + 1; i <= s.size(); ++i) { string substr = s.substr(pos, i - pos); if (!isPalindrome(substr)) { continue; } palindromes.push_back(substr); dfs(s, i, palindromes, ret); palindromes.pop_back(); } } bool isPalindrome(string s) { if (s.empty()) return false; int n = s.size(); for (int i = 0; i < n; ++i) { if (s[i] != s[n - i - 1]) return false; } return true; } }; ~~~ ### Java ~~~ public class Solution { /** * @param s: A string * @return: A list of lists of string */ public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<List<String>>(); if (s == null || s.isEmpty()) return result; List<String> palindromes = new ArrayList<String>(); dfs(s, 0, palindromes, result); return result; } private void dfs(String s, int pos, List<String> palindromes, List<List<String>> ret) { if (pos == s.length()) { ret.add(new ArrayList<String>(palindromes)); return; } for (int i = pos + 1; i <= s.length(); i++) { String substr = s.substring(pos, i); if (!isPalindrome(substr)) { continue; } palindromes.add(substr); dfs(s, i, palindromes, ret); palindromes.remove(palindromes.size() - 1); } } private boolean isPalindrome(String s) { if (s == null || s.isEmpty()) return false; int n = s.length(); for (int i = 0; i < n; i++) { if (s.charAt(i) != s.charAt(n - i - 1)) return false; } return true; } } ~~~ ### 源碼分析 回文的判斷采用了簡化的版本，沒有考慮空格等非字母數字字符要求。Java 中 ArrayList 和 List 的實例化需要注意下。Python 中 result 的初始化為[], 不需要初始化為 [[]] 畫蛇添足。C++ 中的`.substr(pos, n)` 含義為從索引為 pos 的位置往后取 n 個(含) 字符，注意與 Java 中區別開來。 ### 復雜度分析 [DFS](# "Depth-First Search, 深度優先搜索")，狀態數最多 O(2n?1)O(2^{n-1})O(2n?1), 故時間復雜度為 O(2n)O(2^n)O(2n), 使用了臨時列表，空間復雜度為 O(n)O(n)O(n). ### Reference - [Palindrome Partitioning 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/palindrome-partitioning/) - soulmachine 的 Palindrome Partitioning