请教一下palindrome partitioning用memoization的问题# JobHunting - 待字闺中
l*t
1 楼
用c++写了一下用memoization的版本，需要84ms过leetcode。不用memoization的话反
而只需要16ms。。。是因为memoization过程中有很多copy导致的吗？如果是这样，面
试过程中用哪种方法比较好呢?（或者代码可以更精简不用这么多copy?...) 毕竟前者
worst case复杂度是o(n^2)，而后者是(2^n)额。。。求版上大神指点 跪谢Orz
class Solution {
public:
vector> partition(string s) {
vector> f(s.size(), vector(s.size()));
isPalindrome(f, s);
return dfs1(f, 0, s);
}
private:
unordered_map>> cache_;
void isPalindrome(vector>& f, const string& s) {
int len = s.size();
for (int i = len - 1; i >= 0; --i) {
for (int j = i; j < len; ++j) {
if (i == j) f[i][j] = true;
else if (j == i + 1) f[i][j] = s[j] == s[i];
else f[i][j] = s[i] == s[j] && f[i+1][j-1];
}
}
}
vector> dfs1(const vector>& f, int pos,
const string&s) {
if(pos >= s.size()) {
return vector>({vector()});
}
string curr_substr = s.substr(pos);
if(cache_.find(curr_substr) != cache_.end()) return cache_[curr_
substr];
vector> curr_partitions;
for(int i = pos; i < s.size(); ++i) {
if(f[pos][i]) {
vector> suffix_partitions = dfs1(f, i + 1, s);
for(auto& suffix_partition : suffix_partitions) {
vector curr_partition {s.substr(pos, i - pos + 1
)};
if(!suffix_partition.empty())
curr_partition.insert(curr_partition.end(), suffix_
partition.begin(), suffix_partition.end());
curr_partitions.push_back(curr_partition);
}
}
}
cache_[curr_substr] = curr_partitions;
return cache_[curr_substr];
}
};
而只需要16ms。。。是因为memoization过程中有很多copy导致的吗？如果是这样，面
试过程中用哪种方法比较好呢?（或者代码可以更精简不用这么多copy?...) 毕竟前者
worst case复杂度是o(n^2)，而后者是(2^n)额。。。求版上大神指点 跪谢Orz
class Solution {
public:
vector
vector
isPalindrome(f, s);
return dfs1(f, 0, s);
}
private:
unordered_map
void isPalindrome(vector
int len = s.size();
for (int i = len - 1; i >= 0; --i) {
for (int j = i; j < len; ++j) {
if (i == j) f[i][j] = true;
else if (j == i + 1) f[i][j] = s[j] == s[i];
else f[i][j] = s[i] == s[j] && f[i+1][j-1];
}
}
}
vector
const string&s) {
if(pos >= s.size()) {
return vector
}
string curr_substr = s.substr(pos);
if(cache_.find(curr_substr) != cache_.end()) return cache_[curr_
substr];
vector
for(int i = pos; i < s.size(); ++i) {
if(f[pos][i]) {
vector
for(auto& suffix_partition : suffix_partitions) {
vector
)};
if(!suffix_partition.empty())
curr_partition.insert(curr_partition.end(), suffix_
partition.begin(), suffix_partition.end());
curr_partitions.push_back(curr_partition);
}
}
}
cache_[curr_substr] = curr_partitions;
return cache_[curr_substr];
}
};