使用遞歸的FindSpaces方法java

我正在嘗試編寫一個方法，它接受一個字符串的輸入，並通過檢查字符串的部分字符是否與字典單詞匹配來返回列表中可能包含邏輯空間的字符串。例如：使用遞歸的FindSpaces方法java

例子：

input: "becausetodayuseat" 
Output: { 
    "be cause to day us eat ", 
    "be cause to day use at ", 
    "be cause today us eat ", 
    "be cause today use at ", 
    "because to day us eat ", 
    "because to day use at ", 
    "because today us eat ", 
    "because today use at " 
}

我的代碼是目前

public static String[] space(String[] dict, String s) { 
    LinkedList<String> ret = new LinkedList<String>(); 

    // base case 

    if (s.length() == 0) { 
     String[] r = { "" }; 
     return r; 
    } 


    for (int i = 1; i < s.length(); i++) { 
     String prefix = s.substring(0, i); 
     if (inDictionary(dict, prefix)) { 
      prefix = prefix + " "; 
      ret.add(prefix); 
      String suffix = s.substring(i); 
      String[] end = space(dict,suffix); 
      //System.out.println(end.length); 
      for (int j = 0; j < end.length; ++j) { 
       ret.add(end[j]); 
      } 

     } 
    } 

    // This line converts LinkedList<String> to String [] 
    return ret.toArray(new String[0]);

我知道for循環的問題，但我似乎無法找到的bug。我打印出

be 
cause 
to 
day 
us 
use 
a 
today 
us 
use 
a 
because 
to 
day 
us 
use 
a 
today 
us 
use 
a

任何幫助，將不勝感激:)

來源

2017-03-15 cart2003

詳細地談一談究竟是不是爲你工作。我在您的帖子中看不到問題 – Coder

我重新格式化了預期和實際產出;我希望澄清事情。 – Prune

歡迎來到StackOverflow。請閱讀並遵守幫助文檔中的發佈準則。 [最小，完整，可驗證的示例]（http://stackoverflow.com/help/mcve）適用於此處。在發佈您的MCVE代碼並準確描述問題之前，我們無法爲您提供有效的幫助。具體而言，您發佈的代碼應該會生成給定的輸出。你的並不是獨立運行的。 – Prune

通過思考它沒有提供實際執行：

在每一步中，我們可以添加一個空格，或無法添加空間。我們可以把這個問題想象成一棵二叉樹。如果當前「活動序列」是一個單詞，那麼在樹的每一步我們都會添加一個空格，並且我們也嘗試不添加空格。讓我們來看看輸入because

b不是一個單詞，所以我們繼續"" + space("because")這是一個詞，現在我們有"be " + space("cause")和space("because")。

而且我們繼續，直到基本情況。

來源

2017-03-15 19:34:22 marisbest2

編輯：對不起，讀快，它只給出一個結果。我再想想

試試這個

public String parse(String s, HashMap<String, String> map,String dict[]) { 
    if (map.containsKey(s)) { 
     return map.get(s); 
    } 
    if (inDictionary(s)) { 
     return s; 
    } 
    for (int left = 1; left < s.length(); left++) { 
     String leftSub = s.substring(0, left); 
     if (!inDictionary(leftSub)) { 
      continue; 
     } 
     String rightSub = s.substring(left); 
     String rightParsed = parse(rightSub, map,dict); 
     if (rightParsed != null) { 
      String parsed = leftSub + " " + rightParsed; 
      map.put(s, parsed); 
      return parsed; 
     } 
    } 
    map.put(s, null); 
    return null; 
}

要叫它： Your_object.parse（Your_string，新的HashMap（），Your_dict）

來源

2017-03-15 19:44:27 Incognito

您現在正在添加前綴和後綴分開。一旦你找到一個單詞，你需要追加所有可能的後綴，然後將它添加到你的收藏。

僞代碼：

if word found 
    foreach end in ends 
     result.add(word + ' ' + end)

來源

2017-03-15 19:46:16

使用遞歸的FindSpaces方法java

回答

相關問題