[LeetCode]131. Palindrome Partitioning

Problem

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

]

Solution

解析

回溯法。解决方法和求字符串排列结果类似。这里因为是回文串,每次从0开始,回文串长度从1变化到str.size();尝试一次划分,如果划分结果是回文串,插入到划分结果中,如果不是,尝试下一个长度。终止条件是index指向字符串末尾’\0’. 值得注意的是,回溯法,最好调用递归之后,进行回溯,返回到原来的状态,否则,容易出错(没错就是你!)。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<vector<string>> partition(string s) {
if (s.empty()) return {};
vector<string> temp;
vector<vector<string>> res;
helper(s, 0, temp, res);

return res;
}
private:
void helper(string str, int start, vector<string> &temp, vector<vector<string>> &res){
if (start == str.size()){
res.push_back(temp);
//return; 去掉后,运行速度反而更快了,不太理解
}
for (int i = 1; i<= str.size()-start; ++i){
if (judge(str.substr(start, i))){
temp.push_back(str.substr(start, i));
helper(str, start+i, temp, res);
temp.pop_back();
}
}
}
bool judge(string str){
int lo = 0, hi = str.size() - 1;
while (lo <= hi){
if (str[lo] != str[hi]) return false;
lo++; hi--;
}
return true;
}
};
您的支持就是我更新的最大动力!谢谢!