博文中会简要介绍Leetcode P0131题目分析及解题思路。
“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.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
以下是Java的题解代码实现。
class Solution {
public List<List<String>> partition(String s) {
int N = s.length();
boolean[][] dp = new boolean[N][N];
char[] chars = s.toCharArray();
for (int idx=0; idx<N; ++idx) {
dp[idx][idx] = true;
if (idx > 0 && chars[idx] == chars[idx-1])
dp[idx-1][idx] = true;
}
// DP
for (int i1=2; i1<N; ++i1) {
for (int j2=i1-2; j2>=0; --j2) {
dp[j2][i1] = dp[j2+1][i1-1] && (chars[i1] == chars[j2]);
}
}
this.dfs(0, N, s, dp, new ArrayList<>());
return this.partitions;
}
private List<List<String>> partitions = new ArrayList<>();
private void dfs(int left, int N, String s, boolean[][] dp, List<String> partitioning) {
if (left >= N) {
this.partitions.add(new ArrayList<>(partitioning));
return;
}
for (int right=left; right<N; ++right) {
if (!dp[left][right])
continue;
partitioning.add(s.substring(left, right+1));
this.dfs(right+1, N, s, dp, partitioning);
partitioning.remove(partitioning.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<string>> partition(string s) {
int L = s.length();
vector<string> partitioning;
this->_Dfs(0, s, L, partitioning);
return this->partitions_;
}
private:
vector<vector<string>> partitions_;
void _Dfs(int left, const string s, const int L, vector<string> &partitioning) {
if (left >= L) {
this->partitions_.push_back(vector<string>(partitioning));
return;
}
for (int right=left; right<L; ++right) {
if (!this->_Check(s, left, right))
continue;
partitioning.push_back(s.substr(left, right-left+1));
this->_Dfs(right+1, s, L, partitioning);
partitioning.pop_back();
}
}
bool _Check(string s, int left, int right) {
while (left < right) {
if (s[left] != s[right])
return false;
++left;
--right;
}
return true;
}
};