0

我有这个问题要解决

有一个来自用户的输入词，它由两个不同的词组成，例如

AppleCake or BrownPie

现在我们需要开发一个程序，它将接受这个输入并将其与一个词库进行匹配，并将这个词分解成有意义的部分，即 Apple 和 Cake

输入：苹果蛋糕

输出：这个输入有两个词Apple和Cake

输入： RedGrapesWine

输出：这个输入包含三个单词 Red、Grapes 和 Wine

我的问题是：

我应该如何开始解决这个问题？

任何人都可以帮助我解决伪代码/步骤吗？

4

4 回答 4

1

一个非常简单的方法，只有当你的单词数量很少时才有效，那就是遍历单词列表并尝试逐字匹配。

这是一个非常基本的示例（不处理大小写，也不处理单词的多次出现或其他），但它向您展示了如何做：

String input = readFromUser();
String[] dictionary = new String[] { "Apple", "Cake" };
List<String> found = new ArrayList<>();
for (String word : dictionary) {
    int index = input.indexOf(word);
    if (index >= 0) {
        input = input.substring(0, index) + input.substring(index + word.length());
        found.add(word);
    }
}
System.out.println("Found " + found.size() + " words: " + found);

这是非常简单的方法，因为它很耗时。

另一种方法是使用Trie并对其进行导航，直到找到正确的单词（应该是更好的方法）。

于 2012-10-24T10:16:59.697 回答
1

为了改进算法，您应该首先创建一个包含字典包含的所有词开头的集合。如果字典中有“Apple”和“Cake”，则该集合必须包含“A”、“Ap”、“App”、“Appl”、“Apple”、“C”、“Ca”和“Cake”。

因此，如果令牌不能是单词，您会很快看到，因为它的开头与已知单词的开头不匹配。

于 2012-10-25T06:34:42.087 回答
0

如果新词使用大写字母，您可以使用它将单词分成您想要的部分。

于 2012-10-24T09:58:39.670 回答
0

一个简单的解决方案是针对哈希图/字典测试每个可能的分区。

例如

thebody -> t hebody（t 和 hebody 存在吗？）、th ebody（th 和 ebody？）、body（the 和 body？）等。

于 2012-10-24T10:23:45.217 回答