字典树的实现_

C/C++

rhiswell

贴一个仅用智能指针的实现

#include <assert.h>

struct TrieNode {
    static constexpr int kMaxNode = 26;
    static constexpr int to_tnode_idx(char c) {
        return static_cast<int>(c - 'a'); 
    }
    
    int num_word, num_tnode;
    unique_ptr<TrieNode> tnode[kMaxNode];
    
    TrieNode(): num_word(0), num_tnode(0) {
        for (int i = 0; i < kMaxNode; i++) {
            tnode[i] = nullptr;
        }
    };
};

class MyTrie {
  public:
    MyTrie(): root(new TrieNode()) {
        //root = make_unique<TrieNode>();
    }
    
    void insert(string w) {
        insert_rec(root, w);
    }
    void remove(string w) {
        remove_rec(root, w);
    };
    bool search(string w) {
        return search_rec(root, w);
    };
    int prefixNum(string p) {
        int total_word = 0;
        prefix_num_rec(root, p, total_word);
        return total_word;
    };
  private:
    unique_ptr<TrieNode> root;
    
    void insert_rec(unique_ptr<TrieNode> &root, string w) {
        if (w.empty()) {
            root->num_word++;
        } else {
            auto &tnode = root->tnode[TrieNode::to_tnode_idx(w[0])];
            if (tnode == nullptr) {
                tnode = make_unique<TrieNode>();
                root->num_tnode++;
            }
            assert(tnode != nullptr);
            insert_rec(tnode, w.substr(1));
        }
    }
    
    void remove_rec(unique_ptr<TrieNode> &root, string w) {
        if (w.empty()) {
            root->num_word--;
        } else {
            auto &tnode = root->tnode[TrieNode::to_tnode_idx(w[0])];
            //if (tnode == nullptr) return;
            assert(tnode != nullptr);
            remove_rec(tnode, w.substr(1));
            if (tnode->num_word == 0 && tnode->num_tnode == 0) {
                tnode.reset();
                root->num_tnode--;
            }
        }
    }
    
    bool search_rec(unique_ptr<TrieNode> &root, string w) {
        if (w.empty() && root->num_word > 0) return true;
        auto &tnode = root->tnode[TrieNode::to_tnode_idx(w[0])];
        if (tnode == nullptr) return false;
        return search_rec(tnode, w.substr(1));
    }
    
    void prefix_num_rec(unique_ptr<TrieNode> &root, string w, int &total_word) {
        // 2nd, recursively count all the words start with the prefix
        if (w.empty()) {
            total_word += root->num_word;
            for (int i = 0; i < TrieNode::kMaxNode; i++) {
                if (auto &next_tnode = root->tnode[i]; next_tnode != nullptr) {
                    prefix_num_rec(next_tnode, "", total_word);
                }
            }
        } else {
            // 1st, we find the subtree starts with the prefix
            auto &tnode = root->tnode[TrieNode::to_tnode_idx(w[0])];
            if (tnode != nullptr) prefix_num_rec(tnode, w.substr(1), total_word);
        }
    }
};

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
        if (operators.empty()) return {};
        
        vector<string> svec;
        // This var own all the smart pointers
        MyTrie mytrie;
        for (auto &op: operators) {
            auto op_code = op[0], op_val = op[1];
            if (op_code == "1") mytrie.insert(op_val);
            if (op_code == "2") mytrie.remove(op_val);
            if (op_code == "3") svec.push_back(mytrie.search(op_val) ? "YES" : "NO");
            if (op_code == "4") svec.push_back(to_string(mytrie.prefixNum(op_val)));
        }
        
        return svec;
    }
};

发表于 2021-03-31 20:01:35 回复(1)

牛客882991784号

class Solution:
    def __init__(self):
        self.root = {}
        
    def insert(self, word):
        if len(word) > 0:
            cur = self.root
            for c in word:
                if c not in cur:
                    cur[c] = {}
                cur = cur[c]
            cur['#'] = True
    
    def delete(self, word):
        if len(word) > 0 and self.find(word):
            stack = []
            cur = self.root
            is_end = True
            for c in word:
                stack.append(cur) # 不要写成append(cur[c])，我们添加的是从root到倒数第二个节点
                cur = cur[c]
                
            if len(cur) > 1: #判断这个单词是不是最后的词，即不是其他单词的前缀
                is_end = False
                
            for i, c in enumerate(word[::-1]):
                parent = stack.pop()
                if is_end == False:
                    parent[c].pop('#')
                    break
                elif '#' in parent[c] and i == 0:
                    parent.pop(c)
                elif len(parent[c]) == 0:
                    parent.pop(c)

    def search(self, word):
        if self.find(word):
            return 'YES'
        else:
            return 'NO'
        
    def find(self, word):
        if len(word) > 0:
            cur = self.root
            for c in word:
                if c not in cur:
                    return False
                cur = cur[c]
            if '#' in cur:
                return True
        
        return False
    
    def prefixNumber(self, pre):
        cur = self.root
        for c in pre:
            if c not in cur:
                return 0
            cur = cur[c]
        
        return self.countPaths(cur)
    
    def countPaths(self, cur):     
        if len(cur) == 1 and '#' in cur:
            return 1
        
        count = 0
        for c in cur:
            if c == '#':
                count += 1
                continue
            count += self.countPaths(cur[c]) #不要写成self.countPaths(c), c只是一个key，我们要传的是值
            
        return count    
    def trieU(self , operators ):
        # write code here
        rst = []
        for op, word in operators:
            if op == '1':
                self.insert(word)
            elif op == '2':
                self.delete(word)
            elif op == '3':
                rst.append(self.search(word))
            elif op == '4':
                rst.append(str(self.prefixNumber(word)))
        return rst

发表于 2021-01-18 13:23:09 回复(0)

华科菜菜子

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        for(int i=0;i<operators.size();i++)
        {
            if(operators[i][0]=="1")
                addword(operators[i][1]);
            if(operators[i][0]=="2")
                deleteword(operators[i][1]);
            if(operators[i][0]=="3")
                findword(operators[i][1]);
            if(operators[i][0]=="4")
                getnum(operators[i][1]);
        }
        return res;
    }
    private:
    vector<string> allword;
    vector<string> res;
    void addword(string s)
    {
        allword.push_back(s);
        return;
    }
    void deleteword(string s)
    {
        for(int i=0;i<allword.size();i++)
        {
            if(allword[i]==s)
            {
                allword.erase(allword.begin()+i);
                return ;
            }
        }
    }
    void findword(string s)
    {
        int flag=1;
        for(int i=0;i<allword.size();i++)
        {
            if(allword[i]==s)
            {
                flag=0;
                res.push_back("YES");
                break;
            }
        }
        if(flag)
           res.push_back("NO");
        return ;
    }
    void getnum(string s)
    {
        int num=0;
        for(int i=0;i<allword.size();i++)
        {
            if(allword[i].find(s)!=-1)
            {
                num++;
            }
        }
        res.push_back(to_string(num));
        return ;
    }
};

发表于 2020-11-03 16:10:48 回复(2)

威猛的哈士奇

import java.util.*;

class Tire{
Tire children[];
int word_num = 0;
int prefix_num = 0;
boolean isWord = false;
public Tire(){
this.children = new Tire[26];
}
}
public class Solution {
Tire root = new Tire();
// 字符仅是‘a’～‘z’
// void insert(String word)：添加word，可重复添加；
// 如果op为1，则代表添加word
public void insert(String word){
Tire help = root;
char arr[] = word.toCharArray();
for(int i = 0 ; i < arr.length ; i++){
if(help.children[arr[i] - 'a'] == null){// 如果之前无节点
help.children[arr[i] - 'a'] = new Tire(); // 新建节点
}
help = help.children[arr[i] - 'a']; // 移动指针
help.prefix_num++;// 前缀加一
}
// 此处help是最后一个字母所代表的的节点
help.isWord = true;
help.word_num++;// 单词数量加一
}
// void delete(String word)：删除word，如果word添加过多次，仅删除一次；
// op为2则代表删除word
// （数据保证不会删除不存在的word）
public void delete(String word){
Tire help = root;
char arr[] = word.toCharArray();
for(int i = 0 ; i < arr.length ; i++){
help = help.children[arr[i] - 'a'];// help是上一个指针，扫描到当前
help.prefix_num--;// 当前位置前缀和减减
}
help.word_num--;
if(help.word_num == 0){
help.isWord = false;
}
}
// boolean search(String word)查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
// op为3则代表查询word是否在字典树中
public boolean search(String word){
Tire help = root;
char arr[] = word.toCharArray();
for(int i = 0 ; i < arr.length ; i++){
if(help.children[arr[i] - 'a'] == null){
return false; // 没有
}
help = help.children[arr[i] - 'a'];//指针后移
}
// 找到最后
return help.isWord;
}
// int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。
// op为4代表返回以word为前缀的单词数量
public int prefixNumber(String pre){
Tire help = root;
char arr[] = pre.toCharArray();
for(int i = 0 ; i < arr.length ; i++){
if(help.children[arr[i] - 'a'] == null){
return 0; // 没有
}
help = help.children[arr[i] - 'a'];
}
return help.prefix_num;
}
public String[] trieU (String[][] operators) {
// write code here
List<String> list = new ArrayList<>();
for(int i = 0;i < operators.length ; i++){
if(operators[i][0].equals("1")){
insert(operators[i][1]);
}else if(operators[i][0].equals("2")){
delete(operators[i][1]);
}else if(operators[i][0].equals("3")){
boolean flag = search(operators[i][1]);
if(flag){
list.add("YES");
}else{
list.add("NO");
}
}else if(operators[i][0].equals("4")){
int count = prefixNumber(operators[i][1]);
list.add("" + count);
}
}
return list.toArray(new String[list.size()]);
}
}

发表于 2020-12-06 14:08:13 回复(3)

Java

唐氏综合征

吊毛常规解法（说的是我），运气好可以过滴~

import java.util.*;

public class Solution {
    static Map<String, Integer> map = new HashMap<>();
    static List<String> res = new ArrayList<>();

    public static String[] trieU(String[][] operators) {
        for (String[] op : operators) {
            switch (op[0]) {
                case "1":
                    insert(op[1]);
                    break;
                case "2":
                    delete(op[1]);
                    break;
                case "3":
                    search(op[1]);
                    break;
                case "4":
                    prefixNumber(op[1]);
                    break;
                default:
                    System.err.println("Wrong Operate Mode!");
                    break;
            }
        }
        String[] ret = new String[res.size()];
        for (int i = 0; i < res.size(); i++)
            ret[i] = res.get(i);
        return ret;
    }

    static void insert(String word) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }

    static void delete(String word) {
        if (map.containsKey(word)) {
            int count = map.get(word);
            if (count > 1) {
                map.put(word, count - 1);
            } else {
                map.remove(word);
            }
        }
    }

    static void search(String word) {
        res.add(map.containsKey(word) ? "YES" : "NO");
    }

    static void prefixNumber(String pre) {
        int cnt = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet())
            if (entry.getKey().startsWith(pre)) cnt += entry.getValue();
        res.add(String.valueOf(cnt));
    }
}

字典树解法：（大神解法）

1. 将字符串的每个字符都作为一个树的节点，存储所有的字符串的字符节点之间的关系，再利用构建好的字典树，只需要遍历一次，就可以快速判断存在/不存在，以及前缀是否存在的问题，

注意点：在统计前缀个数的时候，需要将前缀字符串的最后一个字符对应的节点的所有子节点的count 值都要统计在内，因为包含两种情况：

1. 以前缀最后一个字符结尾（直接取最后一个节点的 count 值即可）

2. 不以前缀最后一个字符结尾（需要递归处理所有情况，结果包含了 1 中的情况）

import java.util.*;

class TrieNode {
    int count;
    TrieNode[] children;

    public TrieNode() {
        count = 0;
        children = new TrieNode[26];
    }
}

public class Solution {
    static TrieNode root = new TrieNode();
    static List<String> res = new ArrayList<>();

    public static String[] trieU(String[][] operators) {
        for (String[] op : operators) {
            switch (op[0]) {
                case "1":
                    insert(op[1]);
                    break;
                case "2":
                    delete (op[1]);
                    break;
                case "3":
                    search(op[1]);
                    break;
                case "4":
                    prefixNumber(op[1]);
                    break;
                default:
                    System.err.println("Wrong Operate Mode!");
                    break;
            }
        }
        String[] ret = new String[res.size()];
        for (int i = 0; i < res.size(); i++)
            ret[i] = res.get(i);
        return ret;
    }

    static void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null)
                node.children[c - 'a'] = new TrieNode();
            node = node.children[c - 'a'];
        }
        node.count++;
    }

    static void delete (String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null)
                return;
            node = node.children[c - 'a'];
        }
        if (node.count > 0)
            node.count--;
    }

    static void search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                res.add("NO");
                return;
            }
            node = node.children[c - 'a'];
        }
        res.add(node.count > 0 ? "YES" : "NO");
    }

static void prefixNumber(String pre) {
    TrieNode node = root;
    for (char c : pre.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            res.add("0");
            return;
        }
        node = node.children[c - 'a'];
    }
    res.add(String.valueOf(node.count));
}

    static int countWords(TrieNode node) {
        int count = node.count;
        for (TrieNode child : node.children)
            if (child != null)
                count += countWords(child);
        return count;
    }
}

发表于 2024-06-28 15:24:19 回复(0)

Python 3

bytedancers

使用defaultdict和魔法方法getitem和contains

from collections import defaultdict
class Trie:
    def __init__(self):
        self.chars = defaultdict(Trie)
        self.word_num = 0
        self.pre_num = 0

    def __getitem__(self, k):
        return self.chars[k]

    def __contains__(self, k):
        return k in self.chars

    def insert(self, word):
        cur = self
        for ch in word:
            cur[ch].pre_num += 1
            cur = cur[ch]
        cur.word_num += 1

    def delete(self, word):
        cur = self
        for ch in word:
            cur[ch].pre_num -= 1
            cur = cur[ch]
        cur.word_num -= 1

    def search(self, word):
        cur = self
        for ch in word:
            cur = cur[ch]
        return cur.word_num > 0

    def prefixNumber(self, pre):
        cur = self
        for ch in pre:
            cur = cur[ch]
        return cur.pre_num

class Solution:
    def trieU(self , operators ):
        # write code here
        trie = Trie()
        res = []
        for op, t in operators:
            if op == "1":
                trie.insert(t)
            elif op == "2":
                trie.delete(t)
            elif op == "3":
                res.append("YES" if trie.search(t) else "NO")
            elif op == "4":
                res.append(trie.prefixNumber(t))
        return res

发表于 2021-09-04 18:14:24 回复(1)

Java

牛客148901号

import java.util.*;


public class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
        int count = 0;
    }

    class Trie {
        TrieNode root = new TrieNode();

        public void insert(char[] chars) {
            TrieNode node = root;
            for (char ch : chars) {
                int index = ch - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
                node.count++;
            }
            node.isEnd = true;
        }

        public void del(char[] chars) {
            TrieNode node = root;
            for (char ch : chars) {
                int index = ch - 'a';
                node = node.children[index];
                node.count--;
            }
            if (node.count == 0) {
                node.isEnd = false;
            }
        }

        public String search(char[] chars) {
            TrieNode node = root;
            for (char ch : chars) {
                int index = ch - 'a';
                if (node.children[index] == null) {
                    return "NO";
                }
                node = node.children[index];
            }
            return node.isEnd ? "YES" : "NO";
        }

        public String getPrefixWordNum(char[] chars) {
            TrieNode node = root;
            for (char ch : chars) {
                int index = ch - 'a';
                if (node.children[index] != null) {
                    node = node.children[index];
                } else {
                    return "0";
                }
            }
            return String.valueOf(node.count);
        }
    }

    public String[] trieU(String[][] operators) {
        if (operators == null || operators.length == 0) {
            return null;
        }
        int resultSize = 0;
        for (String[] operator : operators) {
            if (operator[0].equals("3") || operator[0].equals("4")) {
                resultSize++;
            }
        }
        String[] result = new String[resultSize];
        int resultIndex = 0;
        Trie trie = new Trie();
        for (String[] operator : operators) {
            String optType = operator[0];
            char[] chars = operator[1].toCharArray();
            if ("1".equals(optType)) {
                trie.insert(chars);
            } else if ("2".equals(optType)) {
                trie.del(chars);
            } else if ("3".equals(optType)) {
                result[resultIndex++] = trie.search(chars);
            } else if ("4".equals(optType)) {
                result[resultIndex++] = trie.getPrefixWordNum(chars);
            }
        }
        return result;
    }
}

发表于 2024-05-10 22:12:36 回复(0)

C++

感谢靓仔赏饭吃

#include <string>
#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
哈希表跟队列都超时了
     */
    vector<string> trieU(vector<vector<string> >& operators) { 
    unordered_map<string, int>hash;
    vector<string>ans;
    for(int i=0;i<operators.size();i++){
        if(operators[i][0]=="1"){
            string key=operators[i][1];
            if(hash.count(key)){
                hash[key]++;
            }else{
                hash[key]=1;
            }
        }
        if(operators[i][0]=="2"){
            string key=operators[i][1];
            if(hash.count(key)&&hash[key]>1){
                hash[key]--;
            }
            if(hash[key]==1){
                hash.erase(key);
            }
        }
        if(operators[i][0]=="3"){
            string key=operators[i][1];
            if(hash.count(key)){
                ans.push_back("YES");
            }else{
                ans.push_back("NO");
            }
        }
        if(operators[i][0]=="4"){
            int num=0;
            string key=operators[i][1];
            int len=key.size();
            for(auto j:hash){
                string temp=j.first.substr(0,len);
                if(temp==key){
                    num=num+j.second;
                }
            }
            ans.push_back(to_string(num));
        }
    }
    return ans;
    }
};

编辑于 2024-04-12 12:38:50 回复(0)

牛客2024007号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
     // 字典树说白了就是多叉树，没有任何区别
    class Tier {
        Tier[] sons;
        // 记录isEnd是为了在search时，避免遍历所有的son
        boolean isEnd;
        int count;
        int prex;
        
        // 根节点，的val是空，是个虚拟节点
        public Tier() {
            sons = new Tier[26];
            // 是不是单词的结尾
            isEnd = false;
            // 单词数
            count  = 0;
            // 前缀数
            prex = 0;
        }

        public void insert(String word) {
            Tier cur = this;
            for(char c : word.toCharArray()) {
                if(cur.sons[c - 'a'] == null) cur.sons[c - 'a'] = new Tier();
                cur = cur.sons[c - 'a'];
                cur.prex++;
            }
            cur.count++;
            cur.isEnd = true;
        }

        public void delete(String word) {
            if(!search(word)) return;
            Tier cur = this;
            for(char c : word.toCharArray()) {
                cur = cur.sons[c - 'a'];
                cur.prex--;
            }
            cur.count--;
            if(cur.count == 0) cur.isEnd = false;
        }

        public boolean search(String word) {
            Tier cur = this;
            for(char c : word.toCharArray()) {
                cur = cur.sons[c - 'a'];
                if(cur == null) return false;
            }
            if(cur.isEnd == true) return true;
            return false;
        }

        public int prefixNumber(String pre) {
            Tier cur = this;
            for(char c : pre.toCharArray()) {
                cur = cur.sons[c - 'a'];
                if(cur == null) return 0;
            }
            return cur.prex;
        }


    }
    public String[] trieU (String[][] operators) {
        Tier t = new Tier();
        ArrayList<String> sb = new ArrayList<>();
        // write code here
        for(String[] cur : operators) {
            switch(cur[0]) {
                case "1" :
                    t.insert(cur[1]);
                    break;
                case "2" :
                    t.delete(cur[1]);
                    break;
                case "3" :
                    if(t.search(cur[1])) sb.add("YES");
                    else sb.add("NO");
                    break;
                case "4" :
                    sb.add(String.valueOf(t.prefixNumber(cur[1])));
                    break;
            }
        }
        return sb.stream().toArray(String[]::new);
   }
}

发表于 2024-01-12 18:51:53 回复(0)

C++

asdfasdq

class Trie {
private:
    vector<Trie*> trie;
    int end = 0;
public:
    Trie() {
        trie.resize(26);
    }
    void insert(string& word) {
        Trie* t = this;
        for (auto c : word) {
            if (t->trie[c - 'a'] == nullptr) {
                t->trie[c - 'a'] = new Trie;
            }
            t = t->trie[c - 'a'];
        }
        t->end++;
    }
    void mdelete(string& word) {
        Trie* t = this;
        for (auto c : word) {
            if (t->trie[c - 'a'] == nullptr) {
                return;
            }
            t = t->trie[c - 'a'];
        }
        if (t->end == 0) return;
        t->end--;
    }
    bool search(string& word) {
        Trie* t = this;
        for (auto c : word) {
            if (t->trie[c - 'a'] == nullptr) {
                return false;
            }
            t = t->trie[c - 'a'];
        }
        return t->end > 0;
    }
private:
    int count;
public:
    int prefixNumber(string& pre) {
        count = 0;
        Trie* t = this;
        for (auto c : pre) {
            if (t->trie[c - 'a'] == nullptr) {
                return 0;
            }
            t = t->trie[c - 'a'];
        }
        count += t->end;
        dfs(t);
        return count;
    }

    void dfs(Trie* t) {
        if (t == nullptr) {
            return;
        }
        for (int i = 0; i < t->trie.size(); ++i) {
            if (t->trie[i] == nullptr) continue;
            count += t->trie[i]->end;
            dfs(t->trie[i]);
        }
    }
};

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        vector<string> res;
        Trie* t = new Trie;
        for (auto v : operators) {
            string op = v[0];
            string ele = v[1];
            if (op == "1") {
                t->insert(ele);
            } else if (op == "2") {
                t->mdelete(ele);
            } else if (op == "3") {
                if (t->search(ele)) {
                    res.push_back("YES");
                } else {
                    res.push_back("NO");
                }
            } else if (op == "4") {
                res.push_back(to_string(t->prefixNumber(ele)));
            }
        }
        return res;
    }

};

发表于 2023-06-12 14:36:26 回复(0)

牛客565269855号

```

public class Solution {

/**

*

* @param operators string字符串二维数组 the ops

* @return string字符串一维数组

*/

public String[] trieU (String[][] operators) {

// write code here

List<String> list = new ArrayList<>();

for(int i=0;i<operators.length;i++){

String[] tmp = operators[i];

String op = tmp[0];

String str = tmp[1];

if("1".equals(op)){

insert(str);

}

else if("2".equals(op)){

delete(str);

}

else if("3".equals(op)){

String res = search(str) ? "YES" : "NO" ;

list.add(res);

}

else{

list.add(prefixNumber(str) + "");

}

return list.toArray(new String[0]);

}

son root = new son();

class son{

son[] sons = new son[26];

int cnt = 0;

}

public void insert(String word){

son t = root;

for(int i=0;i<word.length();i++){

int u = word.charAt(i) - 'a';

if(t.sons[u] == null){

t.sons[u] = new son();

}

t = t.sons[u];

}

t.cnt += 1;

}

public void delete(String word){

son t = root;

for(int i=0;i<word.length();i++){

int u = word.charAt(i) - 'a';

t = t.sons[u];

}

t.cnt -- ;

}

public boolean search(String word){

son t = root;

for(int i=0;i<word.length();i++){

int u = word.charAt(i) - 'a';

if(t.sons[u] == null) return false; // 如果中间节点不存在，返回false

t = t.sons[u];

}

// 当前节点cnt大于0说明该字符串完整的出现过

if(t.cnt > 0) return true;

return false; // 否则说明只是作为前缀出现

}

public int prefixNumber(String pre){

son t = root;

for(int i=0;i<pre.length();i++){

int u = pre.charAt(i) - 'a';

if(t.sons[u] == null) return 0;

t = t.sons[u];

}

int cnt = t.cnt;

for(int i=0;i<26;i++){

if(t.sons[i] != null){

cnt += dfs(t.sons[i]);

}

return cnt;

}

public int dfs(son t){

if(t == null){

return 0;

}

int cnt = t.cnt;

for(int i=0;i<26; i ++){

cnt += dfs(t.sons[i]);

}

return cnt;

}

```

发表于 2023-03-16 21:43:10 回复(0)

Go

小谷围做题家

package main

import "strconv"

/**
 * 
 * @param operators string字符串二维数组 the ops
 * @return string字符串一维数组
*/

type Tree struct{
    node [26]*Tree
    pass int
    tot int
}

func (t *Tree) insert(word string){
    tr:=t
    for _,ch:=range []byte(word){
        if tr.node[int(ch-'a')]==nil{
            tr.node[int(ch-'a')]=&Tree{}
        }
        tr=tr.node[int(ch-'a')]
        tr.pass++
    }
    tr.tot++
}

func (t *Tree) delete(word string){
    tr:=t
    for _,ch:=range []byte(word){
        tr=tr.node[int(ch-'a')]
        tr.pass--
    }
    tr.tot--
}

func (t *Tree) search(word string)bool{
    tr:=t
    for _,ch:=range []byte(word){
        if tr.node[int(ch-'a')]==nil{
            return false
        }
        tr=tr.node[int(ch-'a')]
    }
    return tr.tot>0
}

func (t *Tree) prefixNumber(pre string)int{
    tr:=t
    for i,ch:=range []byte(pre){
        if tr.node[int(ch-'a')]==nil{
            return 0
        }
        tr=tr.node[int(ch-'a')]
        if i==len(pre)-1{
            break
        }
    }
    return tr.pass
}

func trieU( operators [][]string ) []string {
    ans:=[]string{}
    t:=&Tree{}
    for _,child:=range operators{
        x,s:=child[0],child[1]
        if x=="1"{
            t.insert(s)
        }else if x=="2"{
            t.delete(s)
        }else if x=="3"{
            res:=t.search(s)
            if res{
                ans=append(ans,"YES")
            }else{
                ans=append(ans,"NO")
            }
        }else if x=="4"{
            res:=t.prefixNumber(s)
            ans=append(ans,strconv.Itoa(res))
        }
    }
    return ans
}

发表于 2023-03-11 11:12:53 回复(0)

Java

鹏鹏飞

有点想不明白前缀和的答案，如果三个相同的字符串“qwer”插入，pre_number就是3，再删除“qwer”，pre_number就是2。查询“q”的前缀和就是2，难道不应该是0吗？

发表于 2022-12-03 13:46:34 回复(0)

Java

不想喂饭

字典树模板题。Java敲是真的不顺啊，今天模拟面试给我看蒙了

我好菜啊

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    static int[][] trie = new int[1000005][26];
    static int cnt = 0;
    static int[] isEnd = new int[1000005];
    static int[] num = new int[1000005];
    
    public static void insert(String s){
        int rt = 0;
        for(int i=0;i<s.length();i++){
            if(trie[rt][s.charAt(i)-'a'] == 0){
                trie[rt][s.charAt(i)-'a'] = ++cnt;
            }
            rt = trie[rt][s.charAt(i)-'a'];
            num[rt]++;
        }
        isEnd[rt]++;
    }
    
    public static void delete(String s){
        int rt = 0;
        for(int i=0;i<s.length();i++){
            rt = trie[rt][s.charAt(i)-'a'];
            num[rt]--;
        }
        if(isEnd[rt]>0){
            num[rt]--;
            isEnd[rt]--;
        }
    }
    
    public static boolean search(String s){
        int rt = 0;
        for(int i=0;i<s.length();i++){
            if(trie[rt][s.charAt(i)-'a']==0) return false;
            rt = trie[rt][s.charAt(i)-'a'];
        }
        if(isEnd[rt]>=1) return true;
        return false;
    }
    
    public static int prefixNumber(String pre){
        int rt = 0;
        for(int i=0;i<pre.length();i++){
            if(trie[rt][pre.charAt(i)-'a']==0) return 0;
            rt = trie[rt][pre.charAt(i)-'a'];
        }
        return num[rt];
    }
    
    public String[] trieU (String[][] operators) {
        // write code here
        int len = 0;
        for(String[] s:operators){
            if(s[0].equals("3")||s[0].equals("4")) len++;
        }
        String[] ans = new String[len];
        int cnt1 = 0;
        for(String[] s:operators){
            if(s[0].equals("1")){
                insert(s[1]);
            }
            else if(s[0].equals("2")){
                delete(s[1]);
            }
            else if(s[0].equals("3")){
                if(search(s[1]) == true) ans[cnt1++] = "YES";
                else ans[cnt1++] = "NO";
            }
            else{
                ans[cnt1++] = String.valueOf(prefixNumber(s[1]));
            }
        }
        return ans;
    }
}

发表于 2022-01-20 23:46:20 回复(0)

刻苦的大熊猫在度假

java

import java.util.*;

public class Solution {
    public String[] trieU (String[][] operators) {
        // write code here
        List<String> list = new ArrayList<String>();
        DicTree dicTree = new DicTree();
        for(String[] operator : operators){
            int op = Integer.parseInt(operator[0]);
            if(op == 1){
                dicTree.insOrdel(operator[1], 1);
            }else if(op == 2){
                dicTree.insOrdel(operator[1], -1);
            }else if(op == 3){
                boolean res = dicTree.search(operator[1]);
                list.add(res?"YES":"NO");
            }else if(op == 4){
                int num = dicTree.prefixNumber(operator[1]);
                list.add(num+"");
            }
        }
        return list.toArray(new String[list.size()]);
    }
}

class DicTree{
    private int N = 1000009;
    // 统计字符实际占用到数组位置的个数
    int idx = 0;
    // 统计该字符在该格子内出现的次数
    int[] cnt = new int[N];
    // 统计在该格子以该字符结尾的单词数量
    int[] isEnd = new int[N];
    // 使用二维数组维护字典树
    int[][] trees = new int[N][26];
    
    // op == 1?ins:del
    public void insOrdel(String word, int op){
        int p = 0;
        for(int i=0;i<word.length();i++){
            int u = word.charAt(i)-'a';
            if(trees[p][u] == 0){  // 新建一个格子
                trees[p][u] = ++idx;
            }
            p = trees[p][u];
            cnt[p] += op;
        }
        isEnd[p] += op;
    }
    
    public boolean search(String word){
        int p = 0;
        for(int i=0;i<word.length();i++){
            int u = word.charAt(i)-'a';
            if(trees[p][u] == 0) return false;
            p = trees[p][u];
        }
        return isEnd[p]>0;
    }
    
    public int prefixNumber(String prefix){
        int p = 0;
        for(int i=0;i<prefix.length();i++){
            int u = prefix.charAt(i)-'a';
            if(trees[p][u] == 0) return 0;
            p = trees[p][u];
        }
        return cnt[p];
    }
}

发表于 2021-12-04 10:44:04 回复(0)

Python 3

牛客38477449号

class TreeNode:
    def __init__(self):
        self.passn = 0
        self.isend = 0
        self.nextn = [None] * 26


class Solution:
    def trieU(self , operators ):
        # write code here
        if operators == []:
            return []
        root = TreeNode()
        res = []
        for opts in operators:
            opt, s = opts
            if opt == '1':
                self.insert(root, s)
            elif opt == '2':
                self.delete(root, s)
            elif opt == '3':
                res.append(self.search(root, s))
            else:
                res.append(self.prefixNumber(root, s))
        return res

    
    def insert(self, root, word):
        sl = len(word)
        i = 0
        while i < sl:
            node = root.nextn[ord(word[i]) - ord('a')]
            if node:
                node.passn += 1
                root = node
            else:
                node = TreeNode()
                node.passn += 1
                root.nextn[ord(word[i]) - ord('a')] = node
                root = node
            i += 1
        root.isend += 1
        
        
    def delete(self, root, word):
        sl = len(word)
        i = 0
        while i < sl:
            node = root.nextn[ord(word[i]) - ord('a')]
            node.passn -= 1
            root = node
            i += 1
        root.isend -= 1
    
    
    def search(self, root, word):
        sl = len(word)
        i = 0
        while i < sl:
            node = root.nextn[ord(word[i]) - ord('a')]
            root = node
            if root == None:
                return 'NO'
            i += 1
        if root != None and root.isend > 0 and i == sl:
            return 'YES'
        else:
            return 'NO'
    
    
    def prefixNumber(self, root, pre):
        sl = len(pre)
        i = 0
        while i < sl:
            node = root.nextn[ord(pre[i]) - ord('a')]
            if node == None:
                break
            root = node
            i += 1
        return root.passn if i == sl else 0

发表于 2021-09-15 15:59:40 回复(0)

C++

小雨_Amieee

struct Node{
    bool isEnd;
    int countnum;
    map<char,Node*> children;
    Node():isEnd(false),countnum(0) {};
};
class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    Node* root=new Node();
    void insertTrie(string word) {
        Node* node = root;
        for(char c : word){
            if(node->children.find(c)==node->children.end()){
                node->children[c]=new Node();
            }
            node->children[c]->countnum+=1;
            node=node->children[c];
        }
        node->isEnd=true;
    }
    void deleteTrie(string word) {
        Node* node = root;
        for(char c : word){
            if(node->children.find(c)==node->children.end())
                return;
            if(node->children[c]->countnum==1){
                node->children.erase(c);
                return;
            }
            node->children[c]->countnum -=1;
            node = node->children[c];
        }
    }
    bool searchTrie(string word) {
        Node* node = root;
        for(char c : word){
            if(node->children.find(c)==node->children.end())
                return false;
            node = node->children[c];
        }
        return node->isEnd;
    }
    int prefixNumber(string pre) {
        Node* node = root;
        for(char c : pre){
            if(node->children.find(c)==node->children.end())
                return 0;
            node = node->children[c];
        }
        return node->countnum;
    }
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        
        vector<string> result;
        if(operators.size()==0) return result;
        for(int i=0;i<operators.size();i++){
            if(operators[i][0]=="1")
                insertTrie(operators[i][1]);
            if(operators[i][0]=="2")
                deleteTrie(operators[i][1]);
            if(operators[i][0]=="3"){
                if(searchTrie(operators[i][1]))
                   result.push_back("YES");
                else
                   result.push_back("NO");
            }
            if(operators[i][0]=="4")
                result.push_back(to_string(prefixNumber(operators[i][1])));
        }
        return result;
    }
};

发表于 2021-07-28 17:56:55 回复(0)

C++

♿

简单数据结构

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    struct Node{
        bool is_end;
        int cnt;
        Node *son[26];
        Node() {
            is_end = false;
            cnt = 0;
            for(int i=0;i<26;i++) son[i] = nullptr;
        }
    }*root;
    
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        root = new Node();
        vector<string> res;
        for(auto &c:operators){
            if(c[0] == "1") insert(c[1]);
            else if(c[0]=="2") del(c[1]);
            else if(c[0]=="3") res.push_back(search(c[1]) ? "YES" : "NO");
            else if(c[0]=="4") res.push_back(to_string(prefix(c[1])));
        }
        return res;
    }
    void insert(string &s) {
        auto p = root;
        for(auto &c:s) {
            int a = c - 'a';
            if(!p->son[a]) {
                p->son[a] = new Node();
            }
            p->son[a]->cnt ++;
            p = p->son[a];
        }
        p->is_end = 1;
    }
    void del(string &s) {
        if(!search(s)) return ;
        auto p = root;
        for(auto &c:s) {
            int a = c - 'a';
            if(!p->son[a]) return ;
            p->son[a]->cnt--;
            p = p->son[a];
        }
    }
    bool search(string &s) {
        auto p = root;
        for(auto &c:s) {
            int a = c - 'a';
            if(!p->son[a]) return false;
            p = p->son[a];
        }
        return p->is_end && p->cnt;    
    }
    int prefix(string &s) {
        auto p = root;
        for(auto &c:s) {
            int a = c - 'a';
            if(!p->son[a]) return 0;
            p = p->son[a];
        }
        return p->cnt;
    }
};

编辑于 2021-07-21 16:32:39 回复(0)

C

勇敢牛牛，不怕困难！

#include <errno.h>
#include <stdbool.h>
#include <unistd.h>

#define OK 1
#define ERROR -1
#define MEMORY_OVERFLOW -2

typedef int Status;

typedef struct TrieNode {
  int count;       // 这个单词在字典(dictionary)中出现的次数
  struct TrieNode* children[26];
} TrieNode, *PTrieNode;

typedef struct {
  TrieNode* root;
} Trie;

Status InitTrie(Trie* trie) {
  if (!((*trie).root = (PTrieNode) calloc(1, sizeof(TrieNode)))) {
    fprintf(stderr, "InitTrie Memory Overflow: %s\n", strerror(errno));
    exit(MEMORY_OVERFLOW);
  }
  return OK;
}

Status insert(Trie* trie, const char* const word) {
  PTrieNode p = (*trie).root;
  for (const char* c = word; *c; ++c) {
    if (!p->children[*c - 97])
      p->children[*c - 97] = (PTrieNode) calloc(1, sizeof(TrieNode));
    p = p->children[*c - 97];
  }
  ++(*p).count;
  return OK;
}

bool search(Trie* trie, const char* const word) {
  PTrieNode p = (*trie).root;
  for (const char* c = word; *c; ++c) {
    if (!p->children[*c - 97]) return false;
    p = p->children[*c - 97]; 
  }
  return (*p).count > 0;
}

int depth_first_search_algorithm(const PTrieNode root) {
  int i = 0, s = root->count;
  for (i = 0; i < 26; ++i) {
    if (!root->children[i]) continue;
    s += depth_first_search_algorithm(root->children[i]);
  }
  return s;
}

int prefixNumber(Trie* trie, const char* const prefix) {
  PTrieNode p = (*trie).root;
  for (const char* c = prefix; *c; ++c) {
    if (!p->children[*c - 97]) return 0;
    p = p->children[*c - 97]; 
  }
  return depth_first_search_algorithm(p);
}

void rmWord(Trie* trie, const char* const word) {
  PTrieNode p = (*trie).root;
  for (const char* c = word; *c; ++c) {
    if (!p->children[*c - 97]) return;
    p = p->children[*c - 97]; 
  }
  --(*p).count;
}

void destroy(TrieNode* root)  {
  int i;
  for (i = 0; i < 26; ++i) {
    if (!root->children[i]) continue;
    destroy(root->children[i]);
  }
  free(root);
}

Status DestroyTrie(Trie* trie) {
  destroy(trie->root);
  return OK;
}
/**
 * 
 * @param operators string字符串二维数组 the ops
 * @param operatorsRowLen int operators数组行数
 * @param operatorsColLen int* operators数组列数
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 */
char** trieU(char* ** operators, int operatorsRowLen, int* operatorsColLen, int* returnSize) {
  
  usleep(1000 * 1000 - 300000);
  
  Trie trie;
  InitTrie(&trie);
  
  char ** ans = (char**) calloc(1E5, sizeof(char*));
  char tmp[5] = { 0 };
  *returnSize = 0;
  
  int i, op, found, num;
  for (i = 0; i < operatorsRowLen; ++i) {
    op = atoi(**(operators + i));
    switch (op) {
      case 1:
        insert(&trie, *(*(operators + i) + 1));
        break;
      case 2:
        rmWord(&trie, *(*(operators + i) + 1));
        break;
      case 3:
        found = search(&trie, *(*(operators + i) + 1));
        *(ans + (*returnSize)) = (char*) calloc(10, sizeof(char));
        strcpy(*(ans + (*returnSize)++), (found ? "YES" : "NO"));
        break;
      case 4:
        num = prefixNumber(&trie, *(*(operators + i) + 1));
        sprintf(tmp, "%d", num);
        *(ans + (*returnSize)) = (char*) calloc(10, sizeof(char));
        strcpy(*(ans + (*returnSize)++), tmp);
        break;
      default:
        fputs("illegal parameter!", stderr);
        break;
    }
  }
  
  return DestroyTrie(&trie), ans;
}

发表于 2021-07-15 12:22:53 回复(0)

Java

ngcmz7

请大家帮忙看一下，我这统计前缀单词个数的这个方法哪里有问题，为什么个别情况下统计的数量比预期少，看了半天实在想不通哪里错了。。

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    class TreeNode{
        private boolean isEnd;
        private TreeNode[] next;
        
        public TreeNode(){
            isEnd = false;
            next = new TreeNode[26];
        }
    }
    
    TreeNode root = new TreeNode();
    
    public String[] trieU (String[][] operators) {
        List<String> list = new ArrayList<>();
        for(String[] op : operators) {
            String s1 = op[0];
            String s2 = op[1];
            if("1".equals(s1)){
                addTreeNode(s2);
            }else if("2".equals(s1)){
                deleteTreeNode(s2);
            }else if("3".equals(s1)){
                list.add(searchTreeNode(s2));
            }else if("4".equals(s1)){
                list.add(prefixTreeNode(s2));
            }
        }
        String[] ans = new String[list.size()];
        for(int i=0; i<list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    
    public void addTreeNode(String str){
        TreeNode p = root;
        char[] arr = str.toCharArray();
        for(char c : arr){
            int index = c-'a';
            if(p.next[index]==null){
                p.next[index] = new TreeNode();
            }
            p=p.next[index];
        }
        p.isEnd = true;
    }
    
    public void deleteTreeNode(String str) {
        TreeNode p = root;
        char[] arr = str.toCharArray();
        for(char c : arr){
            int index = c-'a';
            if(p.next[index]==null){
                return;
            }
            p=p.next[index];
        }
        p.isEnd=false;
    }
    
    public String searchTreeNode(String str) {
        TreeNode p = root;
        char[] arr = str.toCharArray();
        boolean ans = true;
        for(char c : arr){
            int index = c-'a';
            if(p.next[index]==null){
                ans=false;
                break;
            }
            p=p.next[index];
        }
        if(!p.isEnd) ans=false;
        return ans? "YES" : "NO";
    }
    
    public String prefixTreeNode(String str) {
        TreeNode p = root;
        char[] arr = str.toCharArray();
        int ans = 0;
        for(char c : arr){
            int index = c-'a';
            if(p.next[index]==null){
                return "0";
            }
            p=p.next[index];
        }
        ans = dfsCalculate(p);
        return ans+"";
    }
    
    public int dfsCalculate(TreeNode root){
        TreeNode[] arr = root.next;
        int count=0;
        if(root.isEnd) count+=1;
        for(int i=0; i<arr.length; i++){
            if(arr[i]==null) continue;
            count = count + dfsCalculate(arr[i]);
        }
        return count;           
    }
    
}

发表于 2021-07-13 18:28:17 回复(1)

字典树的实现

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题