Требуется улучшить скорость разрыва слов (динамическое программирование)
Проблема в том, что: учитывая строку s и словарь слов dict, определите, можно ли сегментировать s в разделенную пробелами последовательность из одного или нескольких слов словаря.
Например, учитывая
s = «hithere»,
dict = [«привет», «там»].
Верните true, потому что «hithere» может быть сегментирован как «leet code».
Моя реализация как ниже. Этот код подходит для обычных случаев. Тем не менее, это сильно страдает для ввода, как:
s = «aaaaaaaaaaaaaaaaaaaaaaab», dict = {«aa», «aaaaaa», «aaaaaaaa»}.
Я хочу запомнить обработанные подстроки, однако я не могу сделать это правильно. Любое предложение о том, как улучшить? Большое спасибо!
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int len = s.size();
if(len<1) return true;
for(int i(0); i<len; i++) {
string tmp = s.substr(0, i+1);
if((wordDict.find(tmp)!=wordDict.end())
&& (wordBreak(s.substr(i+1), wordDict)) )
return true;
}
return false;
}
};
Решение
В вашем коде вы не используете динамическое программирование, потому что вы не помните подзадачи, которые вы уже решили.
Вы можете включить это запоминание, например, сохраняя результаты в зависимости от начальной позиции строки s внутри исходной строки или даже на основе ее длины (потому что в любом случае строки, с которыми вы работаете, являются суффиксами исходной строки, и, следовательно, ее длина однозначно определяет ее). Затем, в начале вашего wordBreak Функция, просто проверьте, была ли такая длина уже обработана и, если она имеет, не перезапускать вычисления, просто вернуть сохраненное значение. В противном случае, запустите вычисления и сохраните результат.
Обратите внимание, что ваш подход с unordered_set не позволит вам получить самое быстрое решение. Самое быстрое решение, которое я могу придумать, — это O (N ^ 2), сохраняя все слова в дереве (не на карте!) И следуя этому слову, пока вы идете по заданной строке. Это позволяет достичь O (1) за итерацию цикла, не считая рекурсивный вызов.
Другие решения
Это логически двухэтапный процесс. Найдите все слова из словаря во входных данных, рассмотрите найденные позиции (пары начало / конец), а затем посмотрите, охватывают ли эти слова весь ввод.
Так что вы получите для вашего примера
aa: {0,2}, {1,3}, {2,4}, ... {20,22}
aaaaaa: {0,6}, {1,7}, ... {16,22}
aaaaaaaa: {0,8}, {1,9} ... {14,22}
Это график с узлами 0-23 и кучей ребер. Но узел 23 b полностью недоступен — нет входящего преимущества Теперь это простая проблема теории графов
Найти все места, где встречаются слова из словаря, довольно легко, если ваш словарь организован как три. Но даже std::map можно использовать благодаря его equal_range метод. У вас есть то, что выглядит как O (N * N) вложенный цикл для начальной и конечной позиций, с O (log N) поиском каждого слова. Но вы можете быстро определить, если s.substr(begin,end) все еще жизнеспособный префикс, и какие словарные слова остаются с этим префиксом.
Также обратите внимание, что вы можете построить график лениво. Смотря на begin=0 вы найдете края {0,2}, {0,6} and {0,8}, (И других нет). Теперь вы можете искать узлы 2, 6 и 8. У вас даже есть хороший алгоритм — A *, который предлагает вам сначала попробовать узел 8 (достижимый всего за 1 ребро). Таким образом, вы найдете узлы {8,10}, {8,14} а также {8,16} и т.д. Как видите, вам никогда не понадобится строить часть графика, которая содержит {1,3} как это просто недоступно.
Используя теорию графов, легко понять, почему ваш метод грубой силы выходит из строя. Вы прибываете в узел 8 (aaaaaaaa.aaaaaaaaaaaaaab), и каждый раз ищите подграф с этого момента.
Дальнейшая оптимизация заключается в запуске двунаправленной A *. Это даст вам очень быстрое решение. Во второй половине первого шага вы ищете края, ведущие к 23, b, Поскольку ничего не существует, вы сразу знаете, что узел {23} изолирован
Спасибо за все комментарии. Я изменил свое предыдущее решение на реализацию ниже. На данный момент я не собирался оптимизировать словарь, но эти идеи очень полезны и высоко ценятся.
Как вы думаете, для текущей реализации это может быть улучшено? Спасибо!
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
int len = s.size();
if(len<1) return true;
if(wordDict.size()==0) return false;
vector<bool> dq (len+1,false);
dq[0] = true;
for(int i(0); i<len; i++) {// start point
if(dq[i]) {
for(int j(1); j<=len-i; j++) {// length of substring, 1:len
if(!dq[i+j]) {
auto pos = wordDict.find(s.substr(i, j));
dq[i+j] = dq[i+j] || (pos!=wordDict.end());
}
}
}
if(dq[len]) return true;
}
return false;
}
};
Попробуйте следующее:
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict)
{
for (auto w : wordDict)
{
auto pos = s.find(w);
if (pos != string::npos)
{
if (wordBreak(s.substr(0, pos), wordDict) &&
wordBreak(s.substr(pos + w.size()), wordDict))
return true;
}
}
return false;
}
};
По сути, если вы нашли совпадение, удалите соответствующую часть из входной строки и продолжите тестирование на меньшем входе.