如何防止對wordbreak的無窮遠環

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

我無法通過無限循環的情況下：「aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab」如何防止對wordbreak的無窮遠環

執行輸入：「A」，「AA」，「AAA」，「AAAA 「，」aaaaa「，」aaaaaa「，」aaaaaaa「，」aaaaaaaa「，」aaaaaaaaa「，」aaaaaaaaaa「] 任何人都可以幫助我將錯誤指向邏輯嗎？謝謝

來源

2013-10-31 susanne

什麼是預期的行爲？你能描述一下這個方法應該做什麼嗎？ – thatidiotguy

你可以在調試器中逐步找到你自己的答案。你的一些代碼似乎沒有做任何有用的事情，所以很難說明它應該做什麼。 –

當i = 0時，你真的需要substring（0,0）嗎？ –

你沒有一個無限循環，你有無限遞歸。這是因爲當你用String調用這個方法時，你所做的第一件事情就是調用它自己的字符串。

你也檢查包含（）幾次，但你永遠不會更新字典，所以它不清楚這將是真實的。

執行輸入：[ 「一」，「AA」，「AAA」，「AAAA」，「AAAAA」，「AAAAAA」，「AAAAAAA」，「AAAAAAAA」，「AAAAAAAAA」，「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-31 19:12:41

如何防止對wordbreak的無窮遠環

回答

相關問題