（leetcode问题：139。单词断路）Java解决方案超时 - 回溯解决方案

Question

问题的链接： 139。单词断开 下面的解决方案无法通过所有测试用例并导致超时。我想使用回溯来解决这个问题，但是看来它不起作用。谁能告诉我我的代码中有什么问题？ 此外，这里的解决方案的时间复杂性为O（2^n + n^2）。如何优化它以使其通过所有测试用例？多谢！我真的很感激。

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);
            }
        }
    }
}

Answer 1

某些问题：

• 尝试 all 索引和所有长度匹配所有单词都在做得太多。这些测试中的许多将永远不会成功。例如，如果单词列表仅具有大小为3和4的单词，则仍然与它们相比，其长度大于4是没有意义的。想象一下字符串输入长度为1000的处理。

• 。当两个单词被匹配以获取索引10，但是在s的其余部分中没有什么可用的，您将回溯并尝试其他单词。如果您碰巧找到其他单词以导致索引10，那么尝试再次覆盖其余部分 是没有意义的。众所周知，它将行不通。因此，您应该从尝试未成功的地方注册索引，以便如果您再次到达该索引，就不会重做递归搜索。您可以为此使用布尔数组，每个索引都有一个布尔值。

• 当发现找到时，而不是返回时，当找到是真的时，请突破循环，避免任何进一步的递归调用。

• 使用实例成员使用实例成员是可以的，但是测试框架将在solution>解决方案的同一实例上运行您的代码，以便找到的值的值< /code>在两个测试之间没有重置为false。您必须将重置为false每次调用函数时。但是，我建议您使您的函数返回 boolean值，因此您根本不需要该实例成员。

这是使用上述备注的扰流板解决方案：

类解决方案{
字符串s;
列表WordDict;
布尔失败[];

公共布尔文字break（字符串S，列表WordDict）{
this.s = s;
this.worddict = worddict;
fails = new boolean [s.length（）];
返回回溯（0）;
}

公共布尔回溯（int index）{
if（index == s.length（））返回true;
如果（失败[index]）返回false; //在这里已经尝试过
for（字符串word：worddict）{
if（s.RegionMatches（index，word，0，word.length（）））{
if（BackTrack（index + Word.length（）））返回true;
}
}
失败[index] = true;
返回false;
}
}

Answer 2

通过添加打印语句可以轻松地注意到解决方案的问题。

public void backtrack(String s, List<String> wordDict, int index){
    System.out.println(String.format("Calling function with '%s', index=%d", s, index));
    ....

在这里，如果执行示例测试案例，

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

您会注意到：

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

如您所见（打印语句3和5）同一执行正在发生两次。现在想象一下这是一个非常长的答案。

Answer 3

谢谢大家回答我的问题！我通过回忆修复并优化了解决方案。现在，解决方案可以通过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;
    }
}