Q1: 回文字符串的分割
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"]
]
算法
回溯法.
- 从字符串开头扫描, 找到一个下标i, 使得 str[0..i]是一个回文字符串
- 将str[0..i]记入临时结果中
- 然后对于剩下的字符串str[i+1, end]递归调用前面的两个步骤, 直到i+1 >= end结束
- 这时候, 我们找到了一组结果.
- 开始回溯. 以回溯到最开始的位置i为例. 从i开始, 向右扫描, 找到第一个位置j, 满足str[0..j]为一个回文字符串. 然后重复前面的四个步骤.
以字符串 "ababc" 为例.
- 首先找到 i = 0, "a"为回文字符串.
- 然后在子串"babc"中继续查找, 找到下一个 "b", 递归找到 "a", "b", "c". 至此我们找到了第一组结果. ["a", "b", "a", "b", "c"]
- 将c从结果中移除, 位置回溯到下标为3的"b". 从"b"开始向后是否存在str[3..x]为回文字符串, 发现并没有.
- 回溯到下标为2的"a", 查找是否存在str[2..x]为回文字符串, 发现也没有.
- 继续回溯到下标为1的"b", 查找是否存在str[1..x]为回文字符串, 找到了"bab", 记入到结果中. 然后从下标为4开始继续扫描. 找到了下一个回文字符串"c".
- 我们找到了下一组结果 ["a", "bab", "c"]
- 然后继续回溯 + 递归.
实现
class Solution {
public:
vector<vector<string>> partition(string s) {
std::vector<std::vector<std::string> > results;
std::vector<std::string> res;
dfs(s, 0, res, results);
return results;
}
private:
void dfs(std::string& s, int startIndex,
std::vector<std::string> res,
std::vector<std::vector<std::string> >& results)
{
if (startIndex >= s.length())
{
results.push_back(res);
}
for (int i = startIndex; i < s.length(); ++i)
{
int l = startIndex;
int r = i;
while (l <= r && s[l] == s[r]) ++l, --r;
if (l >= r)
{
res.push_back(s.substr(startIndex, i - startIndex + 1));
dfs(s, i + 1, res, results);
res.pop_back();
}
}
}
};
Q2 回文字符串的最少分割数
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning
["aa","b"] could be produced using 1 cut.
算法
Calculate and maintain 2 DP states:
- dp[i][j] , which is whether s[i..j] forms a pal
- isPalindrome[i], which is the minCut for s[i..n-1]
- Once we comes to a pal[i][j]==true:
- if j==n-1, the string s[i..n-1] is a Pal, minCut is 0, d[i]=0;
- else: the current cut num (first cut s[i..j] and then cut the rest s[j+1...n-1]) is 1+d[j+1], compare it to the exisiting minCut num d[i], repalce if smaller.
d[0] is the answer.
实现
class Solution {
public:
int minCut(std::string s) {
int len = s.length();
int minCut = 0;
bool isPalindrome[len][len] = {false};
int dp[len + 1] = {INT32_MAX};
dp[len] = -1;
for (int leftIndex = len - 1; leftIndex >= 0; --leftIndex)
{
for (int midIndex = leftIndex; midIndex <= len - 1; ++midIndex)
{
if ((midIndex - leftIndex < 2 || isPalindrome[leftIndex + 1][midIndex -1])
&& s[leftIndex] == s[midIndex])
{
isPalindrome[leftIndex][midIndex] = true;
dp[leftIndex] = std::min(dp[midIndex + 1] + 1, dp[leftIndex]);
}
}
std::cout << leftIndex << ": " << dp[leftIndex] << std::endl;
}
return dp[0];
}
};
