Palindrome Partitioning

• tags: [palindrome]

Question

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

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()) {
return;
}

for (int i = pos + 1; i <= s.length(); i++) {
String substr = s.substring(pos, i);
if (!isPalindrome(substr)) {
continue;
}

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


复杂度分析

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