c++ - 如何使用给定特定前缀的 vector 打印出 Trie 中的单词

Question

我目前正在做一个项目，我需要打印出匹配给定前缀的单词，该前缀由用户使用字符串 vector 打印出单词。但是，我在开始使用时遇到了麻烦，希望你们能给我任何建议。

这是我的意思的例子

trie 中的单词 { app, address, add, beg, cow, mice}给定广告前缀使用 vector 打印出包含前缀 ad 的单词:地址添加

非常感谢您提供的任何帮助。

Answer 1

首先，trie 是一棵树。

在 trie 中，所有具有给定前缀(例如 ad)的单词实际上都存储在您的 trie 子树中，在搜索前缀 ad 时会访问该子树。
因此，要打印 trie 中具有给定前缀的所有单词，分两步完成:

1. 找到你的前缀对应的节点node
2. 列出以节点为根的子树中的所有单词。

这是一个伪代码:

find_all_words_starting_with(string prefix, trieNode node, int depth){
    if (depth == length(prefix)){
        suffix = empty_string
        print_all_words_with_prefix(prefix, suffix, node)
    } else {
        letter = prefix[depth]
        if (node.hasChild(letter)){
            find_all_words_starting_with(prefix, node.getChild(letter), depth+1)
        } else { // no word with the correct prefix
            return
        }
    }
}

print_all_words_with_prefix(prefix, suffix, node){
    if (node.isCompleteWord){
        print(prefix + suffix)
    }
    for each letter c in the alphabet {
        if (node.hasChild(c)){
            print_all_words_with_prefix(prefix, suffix + c, node.getChild(c))
        }
    }
}

find_all_words_starting_with 完成工作的第一部分。它找到与前缀对应的节点，并调用第二个函数 print_all_words_with_prefix，这将打印子树中所有完整的单词。