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的复杂度是什么? |
|