【LeetCode】131. Palindrome Partitioning 解题报告（Python & C++）
2024-08-30 13:04:13
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：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]])
和上面思想相同的经典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;
}
};
如果不使用新的函数，只是用题目给的函数也能通过，唯一需要注意的是，当字符串长度是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;
}
};
日期
2018 年 3 月 15 日 ——雾霾消散，春光明媚
2018 年 12 月 21 日 —— 一周就要过去了
最新文章
- code first 创建和初始化数据库
- Spark入门实战系列--8.Spark MLlib（上）--机器学习及SparkMLlib简介
- web安全之sql注入联合查询
- iOS中归档对象的创建，数据写入与读取
- java学习进制转换之查表法
- JAVA基金会 （三）反射 反思的深度分析
- JS获取渲染后的样式
- python 调用 bash （python 调用linux命令）
- 求m和n的最大公约数和最小公倍数
- webstorm中关于vue的一些问题
- Shiro入门之一 -------- Shiro权限认证与授权
- 第一章 初始STM32
- jquery判断设备是否是手机
- 读取 android sys/下的信息
- numpy数组-截取部分
- jvm面试题
- java学习-MD5消息摘要算法
- STM32L476的RTC使用问题记录
- Okhttp之RouteSelector简单解析
- bzoj3680: 吊打XXX（模拟退火）