回文字符串问题可以看做是一个划分链问题,这个和算法导论中介绍动态规划时的矩阵链乘法是一样的,找到一个最优的划分方案。很自然的想到动态规划来得到一个回文串的真值表,然后就是要列举出所有的情况,回溯法可以做到,自然而然的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; };