LeetCode_131: Palindrome Partition 回文字符串

回文字符串问题可以看做是一个划分链问题，这个和算法导论中介绍动态规划时的矩阵链乘法是一样的，找到一个最优的划分方案。很自然的想到动态规划来得到一个回文串的真值表，然后就是要列举出所有的情况，回溯法可以做到，自然而然的DP+BackTracking解决掉。

题目

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”] ]

代码

分析在摘要中都说了，这里注意一下DP时候的细节，就是先单独算两长度的，然后按照长度逐个求解，长串判断需要依赖短串的状态，这是DP的关键。

class Solution {
public:
	vector<vector<string>> partition(string s) {
		const int n = s.size();
		vector<vector<bool>> palin(n, vector<bool>(n, false));
		for (int i = 0; i < n; ++i){
			palin[i][i] = true;
		}
		for (int i = 0; i < n - 1; ++i){
			int j = i + 1;
			palin[i][j] = (s[i] == s[j]);
		}
		for (int len = 2; len < n; ++len){
			for (int i = 0; i < n - len; ++i){
				int j = i + len;
				palin[i][j] = (s[i] == s[j]) && palin[i+1][j-1];
			}
		}
		
		vector<pair<int, int>> chain;
		backtrack(0, n, chain, palin);

		vector<vector<string>> result;
		for (auto sv : record){
			vector<string> ans;
			for (auto sp : sv){
				ans.push_back(s.substr(sp.first, sp.second - sp.first + 1));
			}
			result.push_back(ans);
		}

		return result;
	}

private:
	void backtrack(int start, int bound, vector<pair<int, int>>& chain, vector<vector<bool>>& palin){
		if (start == bound){
			record.push_back(chain);
			return;
		}

		for (int i = start; i < bound; ++i){
			if (palin[start][i]){
				chain.push_back({ start, i });
				backtrack(i + 1, bound, chain, palin);
				chain.pop_back();
			}
		}
		return;
	}
	vector<vector<pair<int, int>>> record;
};