- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址: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 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我有什么: 简单的服务器,配备一个具有 8 个逻辑内核的至强处理器、16 GB 内存、2 个 7200rpm 驱动器的 mdadm raid1。 PostgreSQL 需要处理大量数据。每天导入多达
当消息排入分区队列时,服务总线会检查分区键是否存在。如果找到,它将根据分区键选择片段。 但是当该片段已满时会发生什么,该片段中没有剩余空间。服务总线是否给出错误/消息被丢弃或任何其他片段将用于存储该消
我想知道将集合拆分为子集的有效方法是什么? Iterable> partitions = Iterables.partition(numbers, 10); 或 List> partitions =
有人可以告诉我 DATETIME 列上 HASH PARITION 与 RANGE PARTITION 的优缺点吗?假设我们有一个包含 2000 万条记录的 POS 表,并且想要根据交易日期的年份创建
我们有一个 cosmos-db 容器,其中包含大约 1M 条记录,其中包含有关客户的信息。 documentDb 的分区键是 customerId,它保存客户的唯一 GUID 引用。我已阅读parti
因此,我在写入数据库的步骤中有 2 个分区。我想记录每个分区写入的行数,得到总和,打印到日志中; 我正在考虑在编写器中使用static变量,并使用Step Context/Job Context在St
Bigquery 文档说可以更新分区表的分区时间到期。而我只能为摄取时间分区表执行此操作。我尝试了以下方法: bq query --use_legacy_sql=false ' CREATE
这是一个两部分的问题: 1) 是否可以根据数据的 ROWID 或其他标识符使用 select 语句检索数据所在分区的名称? 例如。 SELECT DATA_ID, CATEGORY, VALUE, *
注意:这几乎是 this question 的副本区别在于,在这种情况下,源表是日期分区的,而目标表尚不存在。此外,该问题的公认解决方案在这种情况下不起作用。 我试图将一天的数据从一个日期分区表复制到
我已经搜索了很多,但找不到有关以下场景的任何信息。 考虑一个包含超过 500,000 行、约 20 列和约 5 列上的 INDEX 的 InnoDB 表。 当该表处于以下情况时,执行“ALTER TA
如何将分区表(在 Oracle 10g 数据库中)更改为不仅用于分区而且还用于表本身的新表空间?我的意思是,我可以毫无问题地进行以下操作, --sql 改变表 abc 移动分区 abc01 表空间 n
我们正在尝试基于 BigQuery 在云中构建(或者更好地说重建)我们的 DWH。我们决定对原始数据使用“按日期字段分区”表(如“created_date”字段),而不是摄取时间分区,因为通过此功能,
给定一个使用分区的 Spring Batch 作业:
“每个分区中可以有许多键(及其相关值),但任何给定键的记录都在一个分区中。”这是一本著名的hadoop教科书的一行。我没有理解它的第二部分的全部含义,即“但是任何给定键的记录都在一个分区中。”这是否意
Let's say I have an Athena table mytable partitioned by columns A, B, and C.假设我有一个由列A、B和C分区的Athen
我正在寻找一些文档来了解 hive.exec.max.dynamic.partitions 和 hive.exec.max.dynamic.partitions.pernode 之间的区别。 我们什么
我看过一些关于创建分区的表的很好的解释,这些分区是 CLUSTERED BY 和 SORTED BY。这与创建带分区的表,然后使用 CLUSTER BY 填充表(例如使用 INSERT OVERWRI
使用摄取时间分区表,可以免费查询每个分区的行数。字节计费为 0。 SELECT DATE(_PARTITIONTME) AS dd, COUNT(*) FROM ds.ingestion_time_p
此处提供示例项目: https://github.com/codependent/micronaut-aws-lambda-proxy-graal 我在 Amazon AWS 上部署了一个 Micro
是否可以在不指定分区键的情况下通过其 ID 检索文档? 我的理解来自阅读 documentation是当未指定分区键时查询将在所有分区中扇出: The following query does not
我是一名优秀的程序员,十分优秀!