0
public boolean wordBreak(String s, Set<String> dict) {

    if(s.length()==0)  return true;

    String first = null;
    boolean isOk= false;

    for(int i=1; i<s.length(); i++){
        first = s.substring(0,i);
        if(dict.contains(first)){
            String remaining = s.substring(i);
            isOk = wordBreak(remaining, dict);
            if(dict.contains(remaining))
                isOk=true;
            if(isOk)
                return isOk;

        }
    }

    return false;
}

我无法通过此案例的无限循环:“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

执行输入:["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaaa","aaaaaaaa","aaaaaaaaaa","aaaaaaaaaa"] 谁能帮我指出逻辑错误?谢谢

4

1 回答 1

1

你没有无限循环,你有无限递归。这是因为当你用一个字符串调用这个方法时,你要做的第一件事就是用相同的字符串调用它自己。

此外,您检查了 contains() 几次,但您从未更新 dict,因此不清楚何时会发生这种情况。

执行输入:["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaaa","aaaaaaaa","aaaaaaaaaa","aaaaaaaaaa"] 谁能帮我指出逻辑错误?

几点

  • 您不会在dict任何地方更新集合。
  • 您使用相同的参数调用相同的函数,因此它将不断重复。
  • 如果这就是您所需要的,那么一个循环或一对循环会更简单,并且更有可能工作。

我不确定它到底做了什么,但你可以做的是

public void wordBreak(String s, Set<String> dict) {
    for(int i = 0; i < s.length(); i++)
        for(int j = i + 1; j < s.length(); j++)
            dict.add(s.substring(i, j));
}
于 2013-10-31T19:12:41.823 回答