Вот вопрос динамического программирования: (leetcode 139) Если задана непустая строка s и словарь wordDict, содержащий список непустых слов, определить, можно ли s сегментировать в пробел.разделенная последовательность из одного или нескольких слов словаря.
Примечание:
Одно и то же слово в словаре может быть многократно использовано в сегментации.Вы можете предположить, что словарь не содержит повторяющихся слов.
И мое решение:
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
Set<String> failed = new HashSet<>();
Set<String> success = new HashSet<>();
int maxLength = 0;
int[] letters = new int[256];
for(String word: wordDict){
maxLength = Math.max(maxLength,word.length());
for(int i = 0; i< word.length(); i++){
letters[word.charAt(i)] = 1;
}
set.add(word);
}
for(int i = 0; i< s.length(); i++){
if(letters[s.charAt(i)]==0)
return false;
}
return dp(s,set,maxLength,failed,success);
}
public boolean dp(String s, Set<String> set,int max,Set<String> failed, Set<String> success){
// base case
if(set.contains(s)){
success.add(s);
return true;
}
if(success.contains(s)){
return true;
} // do I have to overload the comperator?
if(failed.contains(s))
return false;
// self call
for(int i = Math.min(max,s.length())-1; i>=0 ; i--){
if(set.contains(s.substring(0,i+1))){
String sub= s.substring(i+1,s.length());
if(success.contains(sub)||dp(sub,set,max,failed,success)){
success.add(s);
return true;
}
}
}
failed.add(s);
// return
return false;
}
}
Основная идея моего решения - 1. проверьте, может ли строка быть AWordInTheDict + rest;если так, проверьте, может ли остальная часть быть той же самой структурой рекурсивно.2. сохранить успешный набор и неудачный набор, чтобы избежать повторяющихся рекурсивных вызовов. Мой вопрос: Несмотря на то, что это решение прошло все тестовые случаи и составляет более 94% других решений, я не смог рассчитать временную сложность этого решения.Я думаю, что без успеха и неудачного набора решение будет работать на экспоненциальном уровне времени.Я думаю, что успех и неудача определенно снизили экспоненциальный уровень, но я не знаю, насколько именно он уменьшается.Так в чем же заключается большое значение этого решения?И еще, есть ли среднее время выполнения (дельта O) для решения?