0

我正在尝试编写一个方法，该方法接受一个字符串的输入，并通过检查字符串的某些部分是否与字典单词匹配，返回一个可能的字符串列表，其中包含逻辑空格。例如：

例子：

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 循环是问题，但我似乎找不到错误。我正在打印

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

任何帮助将不胜感激 ：）

4

3 回答 3

0

编辑：对不起，读得快，它只给出一个结果。我再想想

尝试这个

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,new HashMap(),Your_dict)

于 2017-03-15T19:44:27.947 回答
0

您现在分别添加前缀和后缀。找到一个单词后，您需要为其添加所有可能的后缀，然后将其添加到您的集合中。

伪代码：

if word found
    foreach end in ends
        result.add(word + ' ' + end)
于 2017-03-15T19:46:16.967 回答
0

在不提供实际实现的情况下仔细考虑：

在每个步骤中，我们可以添加空格，也可以不添加空格。我们可以把这个问题想象成一棵二叉树。如果当前“活动序列”是一个单词，我们在树的每一步都添加一个空格，并且我们也尝试不添加空格。让我们看看输入because

b不是一个词，所以我们继续讨论"" + space("because")哪个是一个词，所以现在我们有了"be " + space("cause")and space("because")。

我们继续直到基本情况。

于 2017-03-15T19:34:22.797 回答