题目地址：https://leetcode.com/problems/palindrome-partitioning/description/
题目描述
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"]
]
题目大意
找出一个字符串可以构成的所有可能回文子字符串。
解题方法
回溯法
看到所有可能的结果的时候，一般想到回溯。
这个题和之前的回溯有个差别，那就是继续开始回溯的条件是目前的结果已经是回文串。然后从后面的字符开始继续回溯。感觉回溯都是套路，80%的代码可以通用的，最好背下来。
特别注意切片的位置，以及path + [s[:i]]产生了新的list中，所以append时候才有效。
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
self.isPalindrome = lambda s : s == s[::-1]
res = []
self.helper(s, res, [])
return res
def helper(self, s, res, path):
if not s:
res.append(path)
return
for i in range(1, len(s) + 1):注意起始和结束位置
if self.isPalindrome(s[:i]):
self.helper(s[i:], res, path + [s[:i]])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
和上面思想相同的经典C++回溯法写法如下：
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
helper(s, res, {});
return res;
}
void helper(string s, vector<vector<string>>& res, vector<string> path) {
if (s.size() == 0) {
res.push_back(path);
return;
}
for (int i = 1; i <= s.size(); i++) {
string pre = s.substr(0, i);
if (isPalindrome(pre)) {
path.push_back(pre);
helper(s.substr(i), res, path);
path.pop_back();
}
}
}
bool isPalindrome(string s) {
if (s.size() == 0) return true;
int start = 0, end = s.size() - 1;
while (start <= end) {
if (s[start] != s[end])
return false;
start ++;
end --;
}
return true;
}
};
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
如果不使用新的函数，只是用题目给的函数也能通过，唯一需要注意的是，当字符串长度是0的时候返回的是空，那么我们没办法在for循环里面进行遍历，所以新增上一个空字符串，最后再去掉。
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
if (s.size() == 0) return res;
for (int i = 1; i <= s.size(); i++) {
string pre = s.substr(0, i);
if (isPalindrome(pre)) {
vector<vector<string>> next = partition(s.substr(i));
if (next.size() == 0)
next.push_back({""});
for (vector<string> vs : next) {
vector<string> path;
path.push_back(pre);
for (string s : vs) {
if (s == "")
continue;
path.push_back(s);
}
res.push_back(path);
}
}
}
return res;
}
bool isPalindrome(string s) {
if (s.size() == 0) return true;
int start = 0, end = s.size() - 1;
while (start <= end) {
if (s[start] != s[end])
return false;
start ++;
end --;
}
return true;
}
};
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 34 35 36 37
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发