LeetCode Palindrome Partitioning

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

本题要求把字符串s分割成若干个子串,使得每个子串都是回文串。如果有多种分割方法,输出所有的分割方案。

很有意思的一道题。我是这样做的:首先用DP求出任意一个子串s[i,...,j]是否为回文串,这就相当于知道了s中那几个位置可以切割;然后就在s中DFS每个割点,求出所有的分割方案。

DP求s[i,...,j]是否为回文串的过程是这样的,如果s[i]==s[j],且dp[i+1][j-1]也是回文串,则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串,然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。

求到了任意一个子串是否为回文串之后,DFS每个割点就好了,这个和枚举排列情况很类似,就不再赘述了。完整代码如下:

class Solution {
private:
	void helper(const string& s, vector<vector<int>>& dp) {
		int n = s.size();
		for (int i = 0; i < n; ++i)dp[i][i] = 1; // 单个字符自身就是回文串
		for (int len = 2; len <= n; ++len) {
			for (int i = 0; i + len - 1 < n; ++i) {
				if (s[i] == s[i + len - 1] && ((i + 1 <= i + len - 2 && dp[i + 1][i + len - 2] == 1) || i + 1 > i + len - 2)) {
					dp[i][i + len - 1] = 1;
				}
			}
		}
	}
	void dfs(const string& s, vector<vector<int>>& dp, vector<vector<string>>& ans, vector<string>& cand,int idx) {
		if (idx == s.size()) {
			ans.push_back(cand);
			return;
		}
		for (int i = idx; i < s.size(); ++i) {
			if (dp[idx][i] == 1) {
				cand.push_back(s.substr(idx, i - idx + 1));
				dfs(s, dp, ans, cand, i + 1);
				cand.pop_back();
			}
		}
	}
public:
	vector<vector<string>> partition(string s) {
		int n = s.size();
		vector<vector<int>> dp(n, vector<int>(n, 0));
		helper(s, dp);
		vector<vector<string>> ans;
		vector<string> cand;
		dfs(s, dp, ans, cand, 0);
		return ans;
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *