前缀搜索简介：使用Trie树

1// 字典树节点类
2class TrieNode
3{
4  	// 指向子节点的指针数组。
5  	// 字典树节点的最大子节点数量可以等于语言字母表的大小。
6   TrieNode children[ALPHABET_SIZE]
7
8  	// isEndOfWord 为 true 表示该节点代表一个单词的结尾
9   boolean isEndOfWord
10}

在字典树中插入单词的伪代码

1void insert(string word)
2{
3    // 将当前节点指向字典树的根节点
4    current_node = root 
5
6    // 遍历给定单词中的所有字符
7    for(每个字符 in string word)
8    {
9        // 如果当前字符没有对应的子节点
10        // 则创建一个新的子节点
11        if(与当前字符关联的子节点为空)
12        {
13            child_node = new TrieNode
14        }
15        // 将当前节点指针移动到子节点
16        current_node = child_node
17    }
18    // 将单词最后一个字符对应的节点标记为单词结尾
19    current_node.isEndOfWord = true
20}

在字典树中搜索单词的伪代码

1boolean search(string word)
2{
3    // 将当前节点指向字典树的根节点
4    current_node = root
5
6    // 遍历给定单词中的所有字符
7    for (每个字符 in string s)
8    {
9        // 搜索在未检查完键的所有字符前终止。
10        // 这是因为字典树路径在遍历和比较键的所有字符之前就已耗尽，
11        // 表明该键不在字典树中。
12        if (与当前字符关联的子节点为空)
13        {
14            return false;
15        }
16
17        // 将当前节点指针移动到子节点
18        current_node = child_node
19    }
20
21    // 如果与单词最后一个字符关联的节点的 isEndOfWord 值为 true，
22    // 表示完整的单词存在于字典树中。
23    // 因此返回 true，否则返回 false。
24    if isEndOfWord 为 true，
25        return true
26    else
27        return false
28}

1boolean isPrefix(string pref)
2{
3    // 将当前节点指向字典树的根节点
4    current_node = root
5
6    // 遍历给定前缀字符串中的所有字符
7    for (每个字符 in String s)
8    {
9        // 搜索在未检查完键的所有字符前终止。
10        // 这是因为字典树路径在遍历和比较键的所有字符之前就已耗尽，
11        // 表明该键不在字典树中。
12        if (与当前字符关联的子节点为空)
13        {
14            return false
15        }
16
17        // 将当前节点指针移动到子节点
18        current_node = child_node
19    }
20
21    // 如果前缀查询字符串的所有字母都成功遍历完毕，
22    // 且搜索过程中未提前终止，则说明前缀字符串存在于字典树中。
23    // 因此返回 true。
24    return true
25}