解析连续字符串中的单词

Question

如果a有一个包含单词且没有空格的字符串,那么鉴于我有一个包含这些单词的词典/列表,我应该如何解析这些单词呢？

例如,如果我的字符串是"thisisastringwithwords",我怎么能用字典创建输出"这是一个带字的字符串"？

我听说使用数据结构Tries可能有所帮助,但也许有人可以帮助使用伪代码？例如,我想也许你可以将字典索引到一个trie结构中,然后沿着trie跟随每个char; 问题是,我不熟悉如何在(伪)代码中执行此操作.

Answer 1

如果您确定字典中包含该短语的所有单词，则可以使用该算法：

String phrase = "thisisastringwithwords";
String fullPhrase = "";
Set<String> myDictionary;
do {
    foreach(item in myDictionary){
        if(phrase.startsWith(item){
            fullPhrase += item + " ";
            phrase.remove(item);
            break;
        }
    }
} while(phrase.length != 0);

有很多复杂的情况，比如，有些项目是平等开始的，所以代码将被更改为使用一些树搜索、BST 等。