- 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 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在解决这个问题 longest palindromic substring leetcode 上的问题,我遵循动态编程方法,创建了一个 n*n bool 表(我猜这也是此问题的标准解决方案)并成功
我是编程新手,所以请多多包涵。我目前正在研究函数逻辑。我正在尝试编写一个函数来查看传递的字符串是否为回文(真或假)。 这是我的代码, function palindrome(word){ if(w
题目地址:https://leetcode.com/problems/super-palindromes/description/ 题目描述 Let's say a positive intege
本文关键词:回文数,回文,题解,Leetcode, 力扣,Python, C++, Java 题目地址:https://leetcode.com/problems/palindrome-number
题目地址:https://leetcode.com/problems/palindrome-partitioning/description/ 题目描述 Given a string s, par
题目地址:https://leetcode.com/problems/valid-palindrome/description/ 题目描述 Given a string, determine if
题目地址:https://leetcode.com/problems/shortest-palindrome/description/ 题目描述 Given a string s, you are
题目地址:https://leetcode.com/problems/palindrome-pairs/description/ 题目描述 Given a list of unique words
题目地址:https://leetcode.com/problems/palindromic-substrings/description/ 题目描述 Given a string, your t
题目地址:https://leetcode.com/problems/longest-palindrome/open in new window Difficulty: Easy 题目描
该程序运行时不会引发任何异常,但无论输入如何,结果始终相同:““空白”是回文。”每次输入都是回文时,我只是想知道是否有人对为什么会发生这种情况有任何建议?下面是该程序的代码: class Palind
我是一名 Java 开发新手。我想用Java编写代码来计算段落中回文词的数量。 假设是:用户可以输入包含尽可能多的句子的段落。每个单词之间以空格分隔,每个句子之间以句点分隔,单词前后的标点符号将被忽略
我正在上一门编程入门类(class),通过 myProgrammingLab 将大量 Material 深入到我们的脑海中。我在递归的概念上遇到了一些麻烦……对我来说它有点被击中或错过了。这个特殊的问
#include using namespace std; void palindrome(char *s){ if (s[1] == 0) { return;
我的一般问题是如何弄清楚如何使用 DFS。这似乎是我知识的薄弱部分。我的想法很模糊,但当问题发生变化时,我经常会卡住。这让我很困惑。 对于这个问题,我卡在了如何用递归编写 DFS 上。给定一个字符串
最长回文子串,题解,leetcode, 力扣,python, C++, java 题目地址:https://leetcode.com/problems/longest-palindromic-sub
题目地址:https://leetcode.com/problems/palindrome-linked-list/#/descriptionopen in new window 题目描述 Giv
题目地址:https://leetcode.com/problems/longest-palindromic-subsequence/description/ 题目描述 Given a strin
这是一些代码,以“直接样式”确定列表是否是 n+1 比较中的回文 pal_d1 :: Eq a => [a] -> Bool pal_d1 l = let (r,_) = walk l l in r
这个问题在这里已经有了答案: String replace method is not replacing characters (5 个答案) 关闭 2 年前。 我正在努力理解我的代码对于这个 L
我是一名优秀的程序员,十分优秀!