使用递归的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

回答

相关问题