The link to the question: 139. Word Break The solution below can not passed all the test cases and lead to timeout. I want to use backtracking to solve this question, however it seems that it doesn't work. Can anyone tell me what's wrong in my code? Besides, the solution here its time complexity is O(2^n n^2). How can I optimize it so that it can pass all test cases? Thanks a lot! I really appreciate it.
class Solution {
boolean found;
public boolean wordBreak(String s, List<String> wordDict) {
backtrack(s, wordDict, 0);
return found;
}
public void backtrack(String s, List<String> wordDict, int index){
if(found == true) return;
if(index == s.length()){
found = true;
return;
}
for(int len = 1; index len <= s.length(); len ){
String prefix = s.substring(index, index len);
if(wordDict.contains(prefix)){
backtrack(s, wordDict, index len);
}
}
}
}
CodePudding user response:
Some issues:
Trying at all indices and all lengths to match all words is doing way too much. Many of those tests will never succeed. For instance, if the list of words only has words of sizes 3 and 4, it makes no sense to still compare with them for lengths that are greater than 4. Imagine the processing when the string input has a length of 1000.
When two words have been matched to get to index 10, but nothing works to cover for the remaining part of
s
, you'll backtrack and try other words. If you then happen to find other words to lead up to index 10, it makes no sense to try to cover for the remaining part again. It is already known that it will not work. So you should register the index from where an attempt was not successful, so that if ever you arrive at that index again, you'll not redo the recursive search. You can use a boolean array for this, with a boolean for each index.Instead of returning when
found
is already true, break out of the loop whenfound
is true, avoiding any further recursive calls.Using an instance member
found
is fine, but the test framework will run your code on the same instance ofSolution
, so that the value offound
is not reset tofalse
between two tests. You must resetfound
tofalse
every time the function is called. I would however suggest to make your function return that boolean value, so you don't need that instance member at all.
Here is a spoiler solution using the above remarks:
class Solution { String s; List wordDict; boolean fails[]; public boolean wordBreak(String s, List wordDict) { this.s = s; this.wordDict = wordDict; fails = new boolean[s.length()]; return backtrack(0); } public boolean backtrack(int index){ if (index == s.length()) return true; if (fails[index]) return false; // Already tried here for (String word : wordDict) { if (s.regionMatches(index, word, 0, word.length())) { if (backtrack(index word.length())) return true; } } fails[index] = true; return false; } }
CodePudding user response:
The problem of your solution can be easily noticed by adding a print statement.
public void backtrack(String s, List<String> wordDict, int index){
System.out.println(String.format("Calling function with '%s', index=%d", s, index));
....
Here if you execute example test case
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
You will notice:
1. Calling function with 'catsandog', index=0
2. Calling function with 'catsandog', index=3
3. Calling function with 'catsandog', index=7
4. Calling function with 'catsandog', index=4
5. Calling function with 'catsandog', index=7
As you can see (print statements 3 and 5) same execution is happening two times. Now imagine this with a really long answer.