Определить время выполнения кода
Я написал следующий код dp сегодня, он работал нормально, так как получил несколько баллов за отправку (вот проблема). Однако я не могу определить время выполнения моего кода. Я чувствую, что это O(n^2 * log D) но я не могу доказать это.
class Solution {
public:
unordered_map<string, bool> m;
bool wordBreak(string s, unordered_set<string>& wordDict) {
int n = s.length();
string t = "";
for(int i=0;i<n;i++){
t += s.at(i);
//cout << t << endl;
if(wordDict.find(t) != wordDict.end()){
m[t] = true;
string x = "";
for(int j=i+1;j<n;j++){
x += s.at(j);
}
if(x == ""){
return true;
}
if(m.find(x) != m.end()){
if(m[x] == true){
return true;
}else{
continue;
}
}else{
if(wordBreak(x, wordDict)){
m[x] = true;
return true;
}else{
//cout << x << endl;
m[x] = false;
continue;
}
}
}else{
//m[t] = false;
}
}
return false;
}
};
Решение
Кажется, есть O(n*n) сложность. Вы используете запоминание, и каждый шаг вашего алротита производит как минимум 1 новое значение в m, Есть n*n/2 подстроки в любой строке, так что вы найдете решение для всей строки с n * n / 2 проходами в худшем случае.
PS: рассмотрим unordered_map работает с O(1),
РЕДАКТИРОВАТЬ:
Возможно, более уместно рассмотреть unordered_map, работающий с O (n) в вашем случае. m.find нужно будет вычислить хеш для его аргумента, который является строкой. может быть, это будет работать быстрее, если вы храните индексы вместо самой строки.
Другие решения
Прежде всего, я бы переписал следующее (не проверено):
class Solution {
public:
unordered_map<string, bool> m;
bool wordBreak(string s, unordered_set<string>& wordDict)
{
while (!s.empty())
{
int n = s.size() ;
for(int i=0;i<n;i++){
//cout << t << endl;
if(wordDict.find(s.substr(0, i)) != wordDict.end()){
m[t] = true;
s = s.substr(i) ;
break ;
}
return !m.empty();
}
};
Основная идея заключается в том, что как только вы найдете совпадение, вы можете удалить соответствующую часть из строки. Тогда я бы сказал, что это n * logD. В конце концов вы делаете только один проход для цикла. Предполагая, что вы найдете совпадение в м < тогда вы получите новый цикл (n-m).
Вот как я это решил.
bool wordBreak(string s, unordered_set<string>& wordDict) {
if (s.empty()) return true;
vector<bool> dp(s.size(), false);
for (int i = 0; i < dp.size(); ++i)
{
for (int j = i; j >= 0; --j)
{
if (wordDict.find(s.substr(j, i - j + 1)) != wordDict.end() &&
(j == 0 || dp[j - 1]))
{
dp[i] = true;
break;
}
}
}
return dp.back();
}