2014
11-18

# LeetCode-Palindrome Partitioning[DFS]

### 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"]
]

//LeetCode, Palindrome Partitioning
// 时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;  // 一个partition方案
dfs(s, path, result, 0, 1);
return result;
}

// s[0, prev-1]之间已经处理，保证是回文串
// prev 表示s[prev-1]与s[prev]之间的空隙位置，start同理
void dfs(string &s, vector<string>& path,
vector<vector<string>> &result, size_t prev, size_t start) {
if (start == s.size()) { // 最后一个隔板
if (isPalindrome(s, prev, start - 1)) { // 必须使用
path.push_back(s.substr(prev, start - prev));
result.push_back(path);
path.pop_back();
}
return;
}
// 不断开
dfs(s, path, result, prev, start + 1);
// 如果[prev, start-1] 是回文，则可以断开，也可以不断开（上一行已经做了）
if (isPalindrome(s, prev, start - 1)) {
// 断开
path.push_back(s.substr(prev, start - prev));
dfs(s, path, result, start, start + 1);
path.pop_back();
}
}

bool isPalindrome(const string &s, int start, int end) {
while (start < end && s[start] == s[end]) {
++start;
--end;
}
return start >= end;
}
};

//LeetCode, Palindrome Partitioning
// 时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;  // 一个partition方案
DFS(s, path, result, 0);
return result;
}
// 搜索必须以s[start]开头的partition方案
void DFS(string &s, vector<string>& path,
vector<vector<string>> &result, int start) {
if (start == s.size()) {
result.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) { // 从i位置砍一刀
path.push_back(s.substr(start, i - start + 1));
DFS(s, path, result, i + 1);  // 继续往下砍
path.pop_back(); // 撤销上上行
}
}
}
bool isPalindrome(const string &s, int start, int end) {
while (start < end && s[start] == s[end]) {
++start;
--end;
}
return start >= end;
}
};

// LeetCode, Palindrome Partitioning
// 动规，时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
vector<vector<string> > partition(string s) {
const int n = s.size();
bool p[n][n]; // whether s[i,j] is palindrome
fill_n(&p[0][0], n * n, false);
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]);

vector<vector<string> > sub_palins[n]; // sub palindromes of s[0,i]
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j)
if (p[i][j]) {
const string palindrome = s.substr(i, j - i + 1);
if (j + 1 < n) {
for (auto v : sub_palins[j + 1]) {
v.insert(v.begin(), palindrome);
sub_palins[i].push_back(v);
}
} else {
sub_palins[i].push_back(vector<string> { palindrome });
}
}
}
return sub_palins[0];
}
};

Java代码:

public class Solution {

private void init(boolean[][] isPal, String s) {
int len = isPal.length;
for (int i=0; i<len; i++) isPal[i][i] = true;
for (int k=1; k<len; k++)
for (int i=0; i+k<len; i++) {
if (s.charAt(i) != s.charAt(i+k)) continue;
isPal[i][i+k] = (i+1 <= i+k-1) ? isPal[i+1][i+k-1] : true;
}
}

private void helper(String s, int start, List<String> tmpPartition, List<List<String>> ans, boolean[][] isPal) {
if (start >= s.length()){
return;
}
for (int i=start; i< s.length(); i++) {
if (isPal[start][i]) {
helper(s, i+1, tmpPartition, ans, isPal);
tmpPartition.remove(tmpPartition.size() - 1);
}
}
}

public List<List<String>> partition(String s) {
int len = s.length();
boolean[][] isPal = new boolean[len][len];
init(isPal, s);
List<List<String>> ans = new ArrayList<List<String>>();
List<String> tmpPartition = new ArrayList<String>();
helper(s, 0, tmpPartition, ans, isPal);
return ans;
}
}

1. 记得那是大年初一，跟妈妈闹没别扭就赖床死活不起来，爸爸好所歹说多不听，结果老爸拿了我竹子做的宝剑狠狠打了我一顿，然后我一个礼拜都没有理他。