LeetCode208 实现Trie

链接: https://leetcode-cn.com/problems/implement-trie-prefix-tree

题意

尝试建立一个字典树，支持快速插入单词、查找单词、查找单词前缀的功能。

解法

学习一下新姿势字典树
需要使用到的是Trie节点，每个节点会有26个子节点，构成的一棵多叉树

由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 O(n)近似 O(1)的时间内完成搜索，且额外开销非常小

本题中会建立一棵字典树，支持insert, search, startwith三种方法

代码

class TrieNode {
public:
    TrieNode* childNode[26];
    bool isVal;
    TrieNode(): isVal(false) {
        for (int i = 0; i < 26; i++) {
            childNode[i] = nullptr;
        }
    }
        
};
class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }   
    void insert(string word) { // 插入一个单词
        int siz = word.size();
        TrieNode* now = root;
        for (int i = 0; i < siz; i++) {
            int ch = word[i] - 'a';
            if (!now -> childNode[ch]) {
                now -> childNode[ch] = new TrieNode();
            }
            now = now -> childNode[ch];
        }
        now -> isVal = true;
    }
    
    bool search(string word) { // 搜索一个单词是否在字典树中
        int siz = word.size();
        TrieNode* now = root;
        for (int i = 0; i < siz; i++) {
            int ch = word[i] - 'a';
            if (!now -> childNode[ch]) return false;
            now = now -> childNode[ch];
        }
        return now ? now -> isVal : false;
    }
    
    bool startsWith(string prefix) { // 搜索一个前缀是否在字典树中出现过
        int siz = prefix.size();
        TrieNode* now = root;
        for (int i = 0; i < siz; i++) {
            int ch = prefix[i] - 'a';
            if (!now -> childNode[ch]) return false;
            now = now -> childNode[ch];
        }
        return true;
    }
};