C*******n
发帖数: 193 | 1 class Solution {
public:
bool valid(string &str, int st, int ed){
while (st
if (str[ed]!=str[st]){
return false;
}else{
st++;
ed--;
}
}
return true;
}
void find(string s, int st, vector &r, vector > &
res){
if (st>=s.size()){
res.push_back(r);
}else{
for (int i=st;i
if (valid(s,st,i)){
r.push_back(s.substr(st,i-st+1));
find(s,i+1,r,res);
r.pop_back();
}
}
}
}
vector> partition(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > res;
vector r;
find(s,0,r,res);
return res;
}
}; | v****a
发帖数: 236 | 2 注意到 for (int i=st;i
对于backtracking 每次递归，n = n-1
复杂度是n*(n-1)*(n-2)...1 = O(n!) | C*******n
发帖数: 193 | 3 very nice!thank you!
【在 v****a 的大作中提到】
: 注意到 for (int i=st;i: 对于backtracking 每次递归，n = n-1
: 复杂度是n*(n-1)*(n-2)...1 = O(n!)
| a********e
发帖数: 53 | 4 还有valid的时间复杂度呢？这题我看到有的博客里说复杂度是O(2^n), 因为有 n &#
8722; 1 个地方可以砍断,每个地方可断可不断。 |
|
