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 when found 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 of Solution, so that the value of found is not reset to false between two tests. You must reset found to false 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.

CodePudding user response：

Thanks for everyone that reply my question!! I fixed and optimized my solution with memoization. Now, the solution can pass all the test cases on leetcode.

class Solution {
    int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dp(s, wordDict, 0);
    }
    public boolean dp(String s, List<String> wordDict, int i){
        if(i == s.length()) return true;
        if(memo[i] != -1) return memo[i] == 0? false: true;
        for(String word: wordDict){
            int len = word.length();
            if(i   len > s.length()) continue;
            if(!word.equals(s.substring(i, i   len))) continue;
            if(dp(s, wordDict, i   len)){
                memo[i] = 1;
                return true;
            }
        }
        memo[i] = 0;
        return false;
    }
}