前缀树算法模板秒杀五道算法题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：前缀树算法模板秒杀五道算法题

评论礼仪 见这里，违者直接拉黑。

[deepbreath373]

OMG

[mengzhibin]

小板凳坐着

[wuuusicong]

真的OMG。。。。Trie太复杂了也。。还不如拆开来说。。

[bhjghjbhbfghfhfg]

208题，R值设置为英文字母z的ascii + 1 == 123即可

[labuladong]

@bhjghjbhbfghfhfg 理论上 27 就够了，自己去优化就好。

[Jebearssica]

getNode那里的泛型是不是有点问题，直接对模板T的数组children赋char了

[labuladong]

@Jebearssica children 数组里面装的是索引，和泛型没有关系

[zhongweiLeex]

648题 单词替换 代码部分

// 在 Trie 树中搜索最短词根（最短前缀）
        String prefix = set.shortestPrefixOf(words[i]);
        if(prefix != null && !prefix.isEmpty()) {
            // 如果搜索到了，改写为词根
            sb.append(prefix);
        } else {
            // 否则，原样放回
            sb.append(words[i]);
        }

中间需要进行一次判空操作 ， String.isEmpty() 不能对空判断

[zhongweiLeex]

hasKeyWithPattern 超出时间限制 需要维护一个额外记录
不然时间复杂度还是指数级别

[labuladong]

@zhongweiLeex 贴出你的代码

[zhongweiLeex]

@zhongweiLeex 贴出你的代码

• 之前是我表达错误了，实在抱歉，是需要将前面已经匹配的剪枝。然后检查剩下的。这样就不会超出时间限制，（代码格式写的比较烂，再次抱歉！）

• 之前的648题 搜索最短前缀部分，也是需要一个 判断 prefix != null 的操作，因为 String.isEmpty() 好像只能对 字符串判断是否是空字符串，但是不能对 空值（null）判断。

• 在遇到通配符的时候 ，就不维护原来的，新建一个，因为如果前面的都匹配了，那前面的就必要拖着整个回溯了，直接查找后面的就行。

class WordDictionary {
    private Node root = null;
    private int size = 0;

    public WordDictionary() {
    }

    private static class Node {
        boolean end = false;
        Node[] children = new Node[26];
    }

    private Node getNode(Node node , String key){
        Node p = root;
        for (int i = 0; i < key.length(); i++) {
                if (p == null){
                    return null;
                }
                char c = key.charAt(i);
                p = p.children[c-'a'];
        }
        return p;
    }
    public boolean get(String key){
        Node p = getNode(root,key);
        if (p == null || p.end == false){
            return false;
        }
        return p.end;
    }


    public void addWord(String word) {
        root = addWord(root,word,0);
    }
    private Node addWord(Node node , String key, int i){
        if (node  == null){
            node = new Node();
        }
        if (i == key.length()){
            node.end = true;
            return node;
        }
        char c= key.charAt(i);
        node.children[c-'a'] = addWord(node.children[c-'a'],key,i+1);
        return node;
    }


    public boolean search(String word) {
        char[] pattern = word.toCharArray();
        return search(root,pattern,0);
    }
    private boolean search(Node node,char[] pattern,int i){
        if(node == null){
            return false;
        }
        if(i == pattern.length){
            return node.end;
        }
        char c = pattern[i];
        if (c == '.'){
            for (int j = 0; j < 26; j++) {
                if(node == null){
                    return false;
                }
                if (node.children[j] == null){
                    continue;
                }
                Node newNode = node.children[j];
                if (search(newNode,pattern,i+1)){
                    return true;
                }
            }
        }else{
            int k = pattern[i] - 'a';
            if(node == null){
                return false;
            }
            if (node.children[k] == null){
                return false;
            }
            node = node.children[k];
            if (search(node,pattern,i+1)){
                return true;
            }
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

[steinstraveler]

当Trie中只有一个元素的时候，执行remove会不会递归把root结点也删除掉？

[GoingMyWay]

应该是的。不过root被删除了也没关系吧，put的时候会被创新新的root结点的。

[labuladong]

是的，root 可以被删除，插入节点时会重新新建__

[bert82503]

打卡，感谢！

[ZYT2271736429]

我

[MzxlM]

请问set 和 map有特别具体的区别吗？ 我搜了一下感觉依然云里雾里

[MzxlM]

TrieSet 和TrieMap 的区别又是什么呢？ 我觉得所有题目都可以用map直接写呀

[FrankYJY]

其实node里面不用数组，直接用hashmap就行，还省空间

[labuladong]

你确定 hashmap 比数组省空间么……

[Hyuvo]

感觉648直接用string 的join比StringBuilder省事一点呢

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        // put the dict in a trie set and use the shortestPrefixOf method
        TrieSet dict = new TrieSet();
        for (String root : dictionary) {
            dict.add(root);
        }
        
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; ++i) {
            String prefix = dict.shortestPrefixOf(words[i]);
            // if prefix can be found, replace
            if (!prefix.isEmpty()) {
                words[i] = prefix;
            }
            
        }        

        return String.join(" ", words);
    }
}

[Hyuvo]

211 只要把children 数组大小优化成26就不会超时啦

class WordDictionary {
    private final TrieMap<Object> map;
    
    public WordDictionary() {
        map  = new TrieMap<>();
    }
    
    public void addWord(String word) {
        // use key to store word, Object as placehoder
        map.put(word, new Object());
    }
    
    public boolean search(String word) {
        // has '.'
        return map.hasKeyWithPattern(word);
    }
}

class TrieMap<V> {
    private static final int R = 26;
    private int size = 0;
    private class TrieNode<V> {
        V val = null;
        TrieNode<V>[] children = new TrieNode[R];        
    }
    private TrieNode<V> root = null;
    
    // methods
    
    public void put(String word, V val) {
        if (!containsKey(word)) {
            size++;
        }
        root = put(root, word, val, 0);
    }
    
    private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
        if (node == null) {
            node = new TrieNode<>();
        }
        if (i == key.length()) {
            node.val = val;
            return node;
        }
        char c = key.charAt(i);
        node.children[c - 'a'] = put(node.children[c - 'a'], key, val, i + 1);
        return node;        
    }
    
    public boolean hasKeyWithPattern(String pattern) {
        
        return hasKeyWithPattern(root, pattern, 0);
    }
    
    // recursion helper
    private boolean hasKeyWithPattern(TrieNode<V> node, String pattern, int i) {
        if (node == null) {
            // cannot continue
            return false;
        }
        if (i == pattern.length()) {
            // reaches the end
            return node.val != null;
        }
        
        char c = pattern.charAt(i);
        if (c != '.') {
            // if not .
            return hasKeyWithPattern(node.children[c - 'a'], pattern, i + 1);
        } 
            
        for (int j = 0; j < R; ++j) {
            // see every possible char, return if any has val
            if (hasKeyWithPattern(node.children[j], pattern, i + 1)) {
                // as long as one child has this patten
                return true;
            }
            // NOTE: NOT return hasKeyWithPattern(node.children[j], pattern, i + 1);        
        }
        // nothing matched
        return false;
        
    }
    
    private TrieNode<V> getNode(TrieNode<V> node, String key) {
        // search downwards from node
        TrieNode<V> p = node;
        for (int i = 0; i < key.length(); ++i) {
            if (p == null) {
                return null;
            }
            
            char c = key.charAt(i);
            p = p.children[c - 'a'];
        }
        return p;        
    }
    
    private V get(String key) {
        TrieNode<V> x = getNode(root, key);
        if(x == null || x.val == null) {
            return null;
        }
        return x.val;
    }
    
    private boolean containsKey(String key) {
        return get(key) != null;        
    }
    
}

[FrankYJY]

迷惑，，我直接套到design-add-and-search-words-data-structure里面，遇到pattern直接返回竟然比返回所有结果还慢很多，有的尝试直接TLE

[FrankYJY]

好吧，力扣运行速度浮动性太大了，直接从TLE到faster than 85了

[chenxiiang]

有一点没太想清楚，看文章中求字符串最短前缀时，返回的是query.substring(0,i)，但是看完后自己做648题时，发现我的方法中应该是i+1，然后把文章中的TrieMap和TrieSet全部拷进去运行结果也是对的，半天没有想清楚哪里不一样，下面是我的答案。

public class Solution648 {
    static class TrieNode {
        boolean isWord;
        TrieNode[] children = new TrieNode[26];
    }

    TrieNode root = new TrieNode();

    public String replaceWords(List<String> dictionary, String sentence) {
        for (String str : dictionary) {
            add(str);
        }
        StringBuilder sb = new StringBuilder();
        for (String str : sentence.split(" ")) {
            sb.append(shortestPrefixOf(str)).append(" ");
        }
        return sb.substring(0, sb.length() - 1);
    }

    private String shortestPrefixOf(String query) {
        TrieNode p = root;
        for (int i = 0; i < query.length(); i++) {
            int idx = query.charAt(i) - 'a';
            if (p.children[idx] == null) {
                break;
            }
            if (p.children[idx].isWord) {
                return query.substring(0, i + 1);//就是这里
            }
            p = p.children[idx];
        }
        return query;
    }

    private void add(String s) {
        TrieNode p = root;
        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            if (p.children[idx] == null) {
                p.children[idx] = new TrieNode();
            }
            p = p.children[idx];
        }
        p.isWord = true;
    }
}

[chenxiiang]

明白了，我判断的是它的孩子节点的值，文章中判断的是它本身的值，这两种情况中的i是不一样的

[lpdswing]

class TrieNode:
    R = 256

    def __init__(self):
        self.val = None
        self.children = [None for _ in range(self.R)]


class TrieMap:
    R = 256

    def __init__(self):
        self.root = None
        self.size = 0

    def get_node(self, node: TrieNode, key: str) -> TrieNode|None:
        """从node开始搜索key, 若果存在返回对应节点,否则返回None"""
        p = node
        for i in range(len(key)):
            if p is None:
                return None
            c = ord(key[i])
            p = p.children[c]
        return p

    def put(self, key: str, val: any) -> None:
        if not self.contains_key(key):
            self.size += 1
        self.root = self._put(self.root, key, val, 0)

    def _put(self, node: TrieNode, key: str, val: any, i: int):
        if not node:
            node = TrieNode()
        if i == len(key):
            node.val = val
            return node
        c = ord(key[i])
        node.children[c] = self._put(node.children[c], key, val, i+1)
        return node

    def remove(self, key: str):
        """
        删除key
        :param key:
        :return:
        """
        if not self.contains_key(key):
            return
        self.root = self._remove(self.root, key, 0)
        self.size -= 1

    def _remove(self, node: TrieNode, key: str, i: int):
        if not node:
            return None
        if i == len(key):
            node.val = None
        else:
            c = ord(key[i])
            node.children[c] = self._remove(node.children[c], key, i+1)
        if node.val:
            return node
        for c in range(self.R):
            if node.children[c]:
                return node
        return None

    def get(self, key: str):
        x = self.get_node(self.root, key)
        if x is None or x.val is None:
            return None
        return x.val

    def contains_key(self, key: str) -> bool:
        """
        判断key是否存在map中
        :param key:
        :return:
        """
        return bool(self.get(key))

    def has_key_with_prefix(self, prefix: str):
        """
        判断是否存在前缀为prefix的key
        :param prefix:
        :return:
        """
        return bool(self.get_node(self.root, prefix))

    def shortest_prefix_of(self, query: str) -> str:
        """
        从所有key中寻找query的最短前缀
        :param query:
        :return:
        """
        p = self.root
        for i in range(len(query)):
            if p is None:
                return ""
            if p.val is not None:
                return query[:i]
            c = ord(query[i])
            p = p.children[c]
        if p is not None and p.val is not None:
            # query本身就是一个key
            return query
        return ""

    def longest_prefix_of(self, query: str) -> str:
        """
        query最长前缀
        :param query:
        :return:
        """
        p = self.root
        max_len = 0
        for i in range(len(query)):
            if p is None:
                break
            if p.val is not None:
                max_len = i
            c = ord(query[i])
            p = p.children[c]
        if p is not None and p.val is not None:
            return query
        return query[:max_len]

    def keys_with_prefix(self, prefix: str) -> List:
        res = []
        x = self.get_node(self.root, prefix)
        if x is None:
            return res
        # dfs遍历x为根的树
        self._traverse(x, [], res)
        return res

    def _traverse(self, node: TrieNode, path: List, res: List):
        if not node:
            return
        if node.val:
            res.append(''.join(path))
        for c in range(self.R):
            path.append(c)
            self._traverse(node.children[ord(c)], path, res)
            path.pop()

    def has_key_with_pattern(self, pattern):
        return self._has_key_with_pattern(self.root, pattern, 0)

    def _has_key_with_pattern(self, node: TrieNode, pattern: str, i):
        """
        匹配通配符是否存在key
        :param node:
        :param pattern:
        :param i:
        :return:
        """
        if not node:
            return False
        if i == len(pattern):
            # 到头了
            return bool(node.val)
        c = pattern[i]
        if c != '.':
            return self._has_key_with_pattern(node.children[ord(c)], pattern, i+1)
        # 遇到通配符 .
        for j in range(self.R):
            if self._has_key_with_pattern(node.children[j], pattern, i+1):
                return True
        return False

    def keys_with_pattern(self, pattern: str):
        """匹配所有符合pattern的key"""
        res = []
        self._keys_with_pattern(self.root, [], pattern, 0, res)
        return res

    def _keys_with_pattern(self, node: TrieNode, path: List, pattern: str, i: int, res: List):
        if not node:
            return
        if i == len(pattern):
            # pattern 匹配完成
            if node.val:
                res.append(''.join(path))
            return
        c = pattern[i]
        if c == '.':
            for j in range(self.R):
                path.append(chr(j))
                self._keys_with_pattern(node.children[j], path, pattern, i+1, res)
                path.pop()
        else:
            path.append(c)
            self._keys_with_pattern(node.children[ord(c)], path, pattern, i+1, res)
            path.pop()

    def __len__(self):
        return self.size

[goahead656]

leetcode 211题不超时的代码，按照东哥的思路写的

class WordDictionary {

    private static class TrieNode{
        private boolean isEnd=false;
        private TrieNode[] children=new TrieNode[26];
    }

    TrieNode root=null;

    public WordDictionary() {
        root=new TrieNode();
    }
    
    public void addWord(String word) {
        root=put(root,word,0);
    }

    private TrieNode put(TrieNode node,String word,int i){
        if(node==null){
            node=new TrieNode();
        }
        if(i==word.length()){
            node.isEnd=true;
            return node;
        }
        int c=word.charAt(i)-'a';
        node.children[c]=put(node.children[c],word,i+1);
        return node;
    }
    
    public boolean search(String word) {
        return hasKeyWithPattern(root,word,0);
    }

    private boolean hasKeyWithPattern(TrieNode node,String word,int i){
        if(node==null){
            return false;
        }
        if(i==word.length()){
            return node.isEnd;
        }
        char c=word.charAt(i);
        if(c!='.'){
            int b=c-'a';
            return hasKeyWithPattern(node.children[b],word,i+1);
        }
        
        for(int j=0;j<26;j++){
            if(hasKeyWithPattern(node.children[j],word,i+1)){
                return true;
            }
        }
        return false;
    }
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

[GoingMyWay]

再看了一遍，更清晰了！写的非常通俗易懂，把之前学到的知识点都串起来了！

[GoingMyWay]

C++的实现，照着东哥的Java代码翻译的。

#include <string>
#include <vector>
#include <iostream>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;


// ASCII 码个数
const int R = 27;

template<class T>
class TrieNode {
public:
    TrieNode() {
        val = T();
        children = vector<TrieNode*>(R);
    }
    T val;
    vector<TrieNode*> children;
};


// 底层用 Trie 树实现的键值映射
// 键为 string 类型，值为类型 T
template<class T>
class TrieMap {
public:
    TrieMap() {
        root = new TrieNode<T>();
        _size = 0;
    }

    /***** 增/改 *****/

    // 在 Map 中添加 key
    void put(string key, T val) {
        if (!containsKey(key)) {
            // 新增键值对
            _size ++;
        }
        // 需要一个额外的辅助函数，并接收其返回值
        root = put(root, key, val, 0);
    }

    // 定义：向以 node 为根的 Trie 树中插入 key[i..]，返回插入完成后的根节点
    TrieNode<T> * put(TrieNode<T> * node, string key, T val, int i) {
        if (node == nullptr) {
            // 如果树枝不存在，新建
            node = new TrieNode<T>();
        }
        if (i == key.length()) {
            // key 的路径已插入完成，将值 val 存入节点
            node->val = val;
            return node;
        }
        char c = key[i];
        if (checkBound()) c = c - 'a';
        int ttt = (int)c;
        // 递归插入子节点，并接收返回值
        node->children[(int)c] = put(node->children[(int)c], key, val, i + 1);
        return node;
    }

    /***** 删 *****/

    // 删除键 key 以及对应的值
    void remove(string key) {
        if (!containsKey(key)) {
            return;
        }
        // 递归修改数据结构要接收函数的返回值
        root = remove(root, key, 0);
        _size--;
    }

    // 定义：在以 node 为根的 Trie 树中删除 key[i..]，返回删除后的根节点
    TrieNode<T> * remove(TrieNode<T> * node, string& key, int i) {
        if (node == nullptr) {
            return nullptr;
        }
        if (i == key.length()) {
            // 找到了 key 对应的 TrieNode，删除 val
            node->val = T();
        } else {
            char c = key[i];
            if (checkBound()) c = c - 'a';
            // 递归去子树进行删除
            node->children[(int)c] = remove(node->children[(int)c], key, i + 1);
        }
        // 后序位置，递归路径上的节点可能需要被清理
        if (node->val != T()) {
            // 如果该 TireNode 存储着 val，不需要被清理
            return node;
        }
        // 检查该 TrieNode 是否还有后缀
        for (char c = 0; (int)c < R; c++) {
            if (node->children[(int)c] != nullptr) {
                // 只要存在一个子节点（后缀树枝），就不需要被清理
                return node;
            }
        }
        // 既没有存储 val，也没有后缀树枝，则该节点需要被清理
        delete node;
        return nullptr;
    }

    /***** 查 *****/
    // 搜索 key 对应的值，不存在则返回 null
    // get("the") -> 4
    // get("tha") -> null
    T get(string key) {
        TrieNode<T> * x = getNode(root, key);
        if (x == nullptr || x->val == T()) {
            return T();
        }
        return x->val;
    }

    TrieNode<T> * getNode(TrieNode<T>* node, string& key) {
        TrieNode<T> * p = node;
        // 从节点 node 开始搜索 key
        for (int i = 0; i < key.length(); i++) {
            if (p == nullptr) {
                // 无法向下搜索
                return nullptr;
            }
            // 向下搜索
            char c = key[i];
            if (checkBound()) c = c - 'a';
            p = p->children[(int)c];
        }
        return p;
   }

    // 判断 key 是否存在在 Map 中
    // containsKey("tea") -> false
    // containsKey("team") -> true
    bool containsKey(string key) {
        return get(key) != T();
    }

    // 在 Map 的所有键中搜索 query 的最短前缀
    // shortestPrefixOf("themxyz") -> "the"
    string shortestPrefixOf(string query) {
        TrieNode<T> * p = root;
        // 从节点 node 开始搜索 key
        for (int i = 0; i < query.length(); i++) {
            if (p == nullptr) {
                // 无法向下搜索
                return "";
            }
            if (p->val != T()) {
                // 找到一个键是 query 的前缀
                return query.substr(0, i);
            }
            // 向下搜索
            char c = query[i];
            if (checkBound()) c = c - 'a';
            p = p->children[(int)c];
        }

        if (p != nullptr && p->val != T()) {
            // 如果 query 本身就是一个键
            return query;
        }
        return "";
    }

    // 在 Map 的所有键中搜索 query 的最长前缀
    // longestPrefixOf("themxyz") -> "them"
    string longestPrefixOf(string query) {
        TrieNode<T> * p = root;
        // 记录前缀的最大长度
        int maxLen = 0;
        for (int i = 0; i < query.size(); i ++) {
            if (p == nullptr) {
                // 无法向下搜索
                return "";
            }
            if (p->val != T()) {
                // 找到一个键是 query 的前缀
                maxLen = i;
            }
            // 向下搜索
            char c = query[i];
            if (checkBound()) c = c - 'a';
            p = p->children[(int)c];
        }
        if (p != nullptr && p->val != T()) {
            // 如果 query 本身就是一个键
            return query;
        }
        return query.substr(0, maxLen);
    }

    // 搜索所有前缀为 prefix 的键
    // keysWithPrefix("th") -> ["that", "the", "them"]
    vector<string> keysWithPrefix(string prefix) {
        vector<string> res;
        // 找到匹配 prefix 在 Trie 树中的那个节点
        TrieNode<T>* x = getNode(root, prefix);
        if (x == nullptr) {
            return res;
        }
        // DFS 遍历以 x 为根的这棵 Trie 树
        traverse(x, prefix, res);
        return res;
    }

    void traverse(TrieNode<T>* node, string& path, vector<string>& res) {
        if (node == nullptr) {
            // 到达 Trie 树底部叶子结点
            return;
        }

        if (node->val != T()) {
            // 找到一个 key，添加到结果列表中
            res.push_back(path);
        }

        // 回溯算法遍历框架
        for (int c = 0; (int)c < R; c++) {
            // 做选择
            char pc;
            if (checkBound()) pc = c + 'a';
            else pc = c + '0';
            path.push_back(pc);
            traverse(node->children[(int)c], path, res);
            // 撤销选择
            path.pop_back();
        }
    }

    // 判断是和否存在前缀为 prefix 的键
    // hasKeyWithPrefix("tha") -> true
    // hasKeyWithPrefix("apple") -> false
    bool hasKeyWithPrefix(string prefix) {
        // 只要能找到一个节点，就是存在前缀
        return prefix.size() > 0 && getNode(root, prefix) != nullptr;
    }

    // 通配符 . 匹配任意字符，搜索所有匹配的键
    // keysWithPattern("t.a.") -> ["team", "that"]
    vector<string> keysWithPattern(string pattern) {
        vector<string> res;
        string path = "";
        traverse(root, path, pattern, 0, res);
        return res;
    }

    // 遍历函数，尝试在「以 node 为根的 Trie 树中」匹配 pattern[i..]
    void traverse(TrieNode<T> * node, string& path, string& pattern, int i, vector<string>& res) {
        if (node == nullptr) {
            // 树枝不存在，即字符 pattern[i-1] 匹配失败
            return;
        }
        if (i == pattern.size()) {
            // pattern 匹配完成
            if (node->val != T()) {
                // 如果这个节点存储着 val，则找到一个匹配的键
                res.push_back(path);
            }
            return;
        }
        char c = pattern[i];
        if (c == '.') {
            // pattern[i] 是通配符，可以变化成任意字符
            // 多叉树（回溯算法）遍历框架
            for (char j = 0; (int)j < R; j++) {
                path.push_back(j);
                traverse(node->children[(int)j], path, pattern, i + 1, res);
                path.pop_back();
            }
        } else {
            // pattern[i] 是普通字符 c
            path.push_back(c);
            if (checkBound()) c = c - 'a';
            traverse(node->children[(int)c], path, pattern, i + 1, res);
            path.pop_back();
        }
    }

    // 通配符 . 匹配任意字符，判断是否存在匹配的键
    // hasKeyWithPattern(".ip") -> true
    // hasKeyWithPattern(".i") -> false
    bool hasKeyWithPattern(string pattern) {
        return hasKeyWithPattern(root, pattern, 0);
    }

    // 函数定义：从 node 节点开始匹配 pattern[i..]，返回是否成功匹配
    bool hasKeyWithPattern(TrieNode<T> * node, string& pattern, int i) {
        if (node == nullptr) {
            // 树枝不存在，即匹配失败
            return false;
        }
        if (i == pattern.length()) {
            // 模式串走到头了，看看匹配到的是否是一个键
            return node->val != T();
        }
        char c = pattern[i];
        // 没有遇到通配符
        if (c != '.') {
            if (checkBound()) c = c - 'a';
            // 从 node.children[c] 节点开始匹配 pattern[i+1..]
            return hasKeyWithPattern(node->children[(int)c], pattern, i + 1);
        }
        // 遇到通配符
        for (int j = 0; (int)j < R; j++) {
            // pattern[i] 可以变化成任意字符，尝试所有可能，只要遇到一个匹配成功就返回
            if (hasKeyWithPattern(node->children[(int)j], pattern, i + 1)) {
                return true;
            }
        }
        // 都没有匹配
        return false;
    }

    // 返回 Map 中键值对的数量
    int size() {
        return _size;
    }

private:
    TrieNode<T> * root;
    // 当前存在 Map 中的键值对个数
    int _size;
    bool checkBound() {
        return R <= 27;
    }
};


class TrieSet {
public:
    TrieSet() {
        map = TrieMap<int>();
    }

    /***** 增 *****/

    // 在集合中添加元素 key
    void add(string key, int val) {
        map.put(key, val);
    }

    /***** 删 *****/

    // 从集合中删除元素 key
    void remove(string key) {
        map.remove(key);
    }

    /***** 查 *****/
    int get(string key) {
        return map.get(key);
    }

    // 判断元素 key 是否存在集合中
    bool contains(string key) {
        return map.containsKey(key);
    }

    // 在集合中寻找 query 的最短前缀
    string shortestPrefixOf(string query) {
        return map.shortestPrefixOf(query);
    }

    // 在集合中寻找 query 的最长前缀
    string longestPrefixOf(string query) {
        return map.longestPrefixOf(query);
    }

    // 在集合中搜索前缀为 prefix 的所有元素
    vector<string> keysWithPrefix(string prefix) {
        return map.keysWithPrefix(prefix);
    }

    // 判断集合中是否存在前缀为 prefix 的元素
    bool hasKeyWithPrefix(string prefix) {
        return map.hasKeyWithPrefix(prefix);
    }

    // 通配符 . 匹配任意字符，返回集合中匹配 pattern 的所有元素
    vector<string> keysWithPattern(string pattern) {
        return map.keysWithPattern(pattern);
    }

    // 通配符 . 匹配任意字符，判断集合中是否存在匹配 pattern 的元素
    bool hasKeyWithPattern(string pattern) {
        return map.hasKeyWithPattern(pattern);
    }

    // 返回集合中元素的个数
    int size() {
        return map.size();
    }

private:
    // 底层用一个 TrieMap，键就是 TrieSet，值仅仅起到占位的作用
    // 值的类型可以随便设置，我参考 Java 标准库设置成 Object
    TrieMap<int> map;

};

class Trie {
public:
    Trie() {
        s = TrieSet();
    }
    
    void insert(string word) {
        if (!s.contains(word)) {
            s.add(word, 1);
        } else {
            s.add(word, s.get(word)+1);
        }
    }
    
    int countWordsEqualTo(string word) {
        if (!s.contains(word)) return 0;
        return s.get(word);
    }
    
    int countWordsStartingWith(string prefix) {
        int res = 0;
        auto keys = s.keysWithPrefix(prefix);
        for (auto & key: keys) {
            res += s.get(key);
        }
        return res;
    }
    
    void erase(string word) {
        int freq = s.get(word);
        if (freq - 1 == 0) {
            s.remove(word);
        } else {
            s.add(word, freq - 1);
        }
    }

private:
    TrieSet s;
};

int main(int argc, char** argv) {
    Trie trie;
    trie.insert("apple");               // Inserts "apple".
    trie.insert("apple");               // Inserts another "apple".
    int r = trie.countWordsEqualTo("apple");    // There are two instances of "apple" so return 2.
    r = trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2.
    trie.erase("apple");                // Erases one "apple".
    r = trie.countWordsEqualTo("apple");    // Now there is only one instance of "apple" so return 1.
    r = trie.countWordsStartingWith("app"); // return 1
    trie.erase("apple");                // Erases "apple". Now the trie is empty.
    r = trie.countWordsStartingWith("app"); // return 0
    return 0;
}

[huangzy1218]

好复杂啊啊啊

[PvP-zzz]

Memory Limit Exceeded，该怎么办啊啊啊