h**o
发帖数: 548 | 1 Given a string s, partition s such that every substring of the partition is
a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
知道是用backtracking + DP. 但只知道判断是否Palindrome 可以DP. 不知道为何有贴
说有两个地方可以DP？
复杂度如何求？
time: 每个node 分成 n 支， 有n 层树， 难道 是 time = n^n?
space: n (recursive)+ n^2 (存 isPalindrome 的结果） = n^2? | S*****J
发帖数: 18 | 2 两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
思路差不多。
class Solution {
public:
bool isPalindrome(string s, int start, int end)
{
while(start
{
if(s[start]!=s[end])
return false;
start++;
end--;
}
return true;
}
void DFS(string &s, int start, vector &temp, vector
string>> &res)
{
if(start==s.size())
{
res.push_back(temp);
return;
}
for(int i=start; i
{
if(isPalindrome(s, start, i))
{
temp.push_back(s.substr(start, i-start+1));
DFS(s, i+1, temp, res);
temp.pop_back();
}
}
}
vector> partition(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector> res;
vector temp;
DFS(s, 0, temp, res);
return res;
}
}; | h**o
发帖数: 548 | 3 请问你哪里用到DP了？
我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
array 里， 省得老算老算的，我觉得这叫DP.
【在 S*****J 的大作中提到】
: 两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
: 思路差不多。
: class Solution {
: public:
: bool isPalindrome(string s, int start, int end)
: {
:
: while(start: {
: if(s[start]!=s[end])
| S*****J
发帖数: 18 | 4 我表达有这么差劲咩＝。＝？
我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
，这个就是直接往回找就行了。
【在 h**o 的大作中提到】
: 请问你哪里用到DP了？
: 我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
: 我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
: array 里， 省得老算老算的，我觉得这叫DP.
| h**o
发帖数: 548 | 5 明白了。 谢谢。：-）
请问 我说的 Palindrome Partitioning 这道题 time 复杂度 是 n^n 吗？ 如果不是
，那是什么那？
【在 S*****J 的大作中提到】
: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。
| h**o
发帖数: 548 | 6 明白了。 谢谢。：-）
请问 我说的 Palindrome Partitioning 这道题 time 复杂度 是 n^n 吗？ 如果不是
，那是什么那？
【在 S*****J 的大作中提到】
: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。
| h**o
发帖数: 548 | 7 Given a string s, partition s such that every substring of the partition is
a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
知道是用backtracking + DP. 但只知道判断是否Palindrome 可以DP. 不知道为何有贴
说有两个地方可以DP？
复杂度如何求？
time: 每个node 分成 n 支， 有n 层树， 难道 是 time = n^n?
space: n (recursive)+ n^2 (存 isPalindrome 的结果） = n^2? | S*****J
发帖数: 18 | 8 两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
思路差不多。
class Solution {
public:
bool isPalindrome(string s, int start, int end)
{
while(start
{
if(s[start]!=s[end])
return false;
start++;
end--;
}
return true;
}
void DFS(string &s, int start, vector &temp, vector
string>> &res)
{
if(start==s.size())
{
res.push_back(temp);
return;
}
for(int i=start; i
{
if(isPalindrome(s, start, i))
{
temp.push_back(s.substr(start, i-start+1));
DFS(s, i+1, temp, res);
temp.pop_back();
}
}
}
vector> partition(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector> res;
vector temp;
DFS(s, 0, temp, res);
return res;
}
}; | h**o
发帖数: 548 | 9 请问你哪里用到DP了？
我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
array 里， 省得老算老算的，我觉得这叫DP.
【在 S*****J 的大作中提到】
: 两个dp是求最小palindrome切割数的，这道题recursive地往回找就行了，和subsets的
: 思路差不多。
: class Solution {
: public:
: bool isPalindrome(string s, int start, int end)
: {
:
: while(start: {
: if(s[start]!=s[end])
| S*****J
发帖数: 18 | 10 我表达有这么差劲咩＝。＝？
我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
，这个就是直接往回找就行了。
【在 h**o 的大作中提到】
: 请问你哪里用到DP了？
: 我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
: 我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
: array 里， 省得老算老算的，我觉得这叫DP.
| h**o
发帖数: 548 | 11 明白了。 谢谢。：-）
请问 我说的 Palindrome Partitioning 这道题 time 复杂度 是 n^n 吗？ 如果不是
，那是什么那？
【在 S*****J 的大作中提到】
: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。
| h**o
发帖数: 548 | 12 明白了。 谢谢。：-）
请问 我说的 Palindrome Partitioning 这道题 time 复杂度 是 n^n 吗？ 如果不是
，那是什么那？
【在 S*****J 的大作中提到】
: 我表达有这么差劲咩＝。＝？
: 我说：dp不用在这道题，用在找最小palindrome切割数的（是你问的这题的兄弟问题）
: ，这个就是直接往回找就行了。
| c*********n
发帖数: 1057 | 13 同问这题求所有partition的复杂度是什么？ |
|
