字典树的实现_

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)

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)

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

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)

Java

阿尼亚瓦库瓦库

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code dgfdsfgdfg
        ArrayList<String> res = new ArrayList<>();
        ArrayList<String> trieU = new ArrayList<>();
        
        for (int i = 0; i < operators.length; i++) {
            switch(operators[i][0]) {
                case "1" :
                    trieU.add(operators[i][1]);
                    trieU.sort(Comparator.comparing(o->o));
                    break;
                case "2" :
                    for (String s : trieU) {
                        if (s.equals(operators[i][1])) {
                            trieU.remove(s);
                            break;
                        }
                    }
                    break;
                case "3":
                    if (trieU.contains(operators[i][1])) {
                        res.add("YES");
                    } else {
                        res.add("NO");
                    }
                    break;
                case "4":
                    int count = 0;
                    boolean flag = false;
                    for (String s : trieU) {
                        if (s.matches(operators[i][1] + ".*")) {
                            if (!flag) {
                                flag = true;
                            }
                            count++;
                        } else {
                            if (flag) {
                                break;
                            }
                        }
                    }
                    res.add(String.valueOf(count));
            }
        }
        
        String[] result = (String[]) res.toArray(new String[res.size()]);
        return result;
    }
}

感谢运行时长靠前的几位大佬让我改过自新：

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        Trie trie = new Trie();
        
        ArrayList<String> res = new ArrayList<>();
        
        for (String[] operator : operators) {
            switch (operator[0]) {
                case "1" : 
                    trie.insert(operator[1]);
                    break;
                case "2" :
                    trie.delete(operator[1]);
                    break;
                case "3" :
                    res.add(trie.search(operator[1]) ? "YES" : "NO");
                    break;
                case "4" :
                    res.add(String.valueOf(trie.prefixNumber(operator[1])));
            }
        }
        return res.toArray(new String[res.size()]);
    }
}

class Trie {
    
    Trie[] child; // 记录子节点，新建26个代表26个小写字母，如果为空即代表字典树中没有出现该字母
    int count; // 记录根到此节点为前缀的字符串的个数
    boolean isEnd; // 记录该节点是否为一个单词的最后一个字母
    
    public Trie() {
        child = new Trie[26];
        count = 0;
        isEnd = false;
    }
    
    public void insert(String word) {
        
        Trie cur = this;
        
        for (char c : word.toCharArray()) {
            if (cur.child[c - 'a'] == null) {
                cur.child[c - 'a'] = new Trie();
            }
            
            cur = cur.child[c - 'a'];
            cur.count++;
        }
        
        cur.isEnd = true;
    }
    
    public void delete(String word) {
        
        Trie cur = this;
        
        for (char c : word.toCharArray()) {
            if (cur.child[c-'a'] == null){
                return;
            }
            if (cur.child[c - 'a'].count == 1) {
                cur.child[c - 'a'] = null;
                return;
            }
            cur = cur.child[c - 'a'];
            cur.count--;
        }
    }
    
    public boolean search(String word) {
        
        Trie cur = this;
        
         for (char c : word.toCharArray()) {
             if (cur.child[c - 'a'] == null) {
                 return false;
             }
             cur = cur.child[c - 'a'];
         }
        
        return cur.isEnd;
    }
    
    public int prefixNumber(String pre) {
        
        Trie cur = this;
        
        for (char c : pre.toCharArray()) {
            if (cur.child[c - 'a'] == null) {
                 return 0;
            }
            cur = cur.child[c - 'a'];
        }
        
        return cur.count;
    }
}

编辑于 2021-05-26 23:17:31 回复(0)

Java

牛客664154028号

HashMap解法；

public class Solution {
    // 构建树结构；
    class OrderTree{
        private HashMap<String,Integer> map;
        OrderTree(){
            map = new HashMap<>();
        }
        // 插入； 
        public void insert(String word){
            if(map.containsKey(word)){
                int count = map.get(word);
                map.put(word,count+1);
            }else{
                map.put(word,1);
            }
        }
        //  删除；
        public void delete(String word){
            if(map.containsKey(word)){
                int count = map.get(word);
                if(count == 1) map.remove(word);
                else{
                    map.put(word,count-1);
                }
            }
        }
       // 查找；
        public boolean search(String word){
            return map.containsKey(word);
        }
      // 返回前缀单词个数
        public int prefixNumber(String word){
            int res = 0;
            for(String key:map.keySet()){
               if(key.indexOf(word) == 0){
                   res++;
               }
            }
            return res;
        }
    }
    // 主函数；  
    public String[] trieU (String[][] operators) {
        // write code here
        OrderTree tree = new OrderTree();
        List<String> list = new ArrayList<>();
        for(String[] s : operators){
            switch(s[0]){
                case "1":
                    tree.insert(s[1]);
                    break;
                case "2":
                    tree.delete(s[1]);
                    break;
                case "3":
                    if(tree.search(s[1])) list.add("YES");
                    else list.add("NO");
                    break;
                case "4":
                    list.add(String.valueOf(tree.prefixNumber(s[1])));
                    break;
            }
        }
        String[] res = new String[list.size()];
        int index = 0;
        for(String s:list){
               res[index++] = s;
        }
        return res;
    }
}

发表于 2021-04-27 16:54:17 回复(0)

Java

牛客915296776号

import java.util.*;

public class Solution {
    public String[] trieU (String[][] operators) {
        List<String> list = new ArrayList<>();
        root = new TrieNode('0');
        for (String[] op : operators) {
            if (op[0].equals("1")) insert(op[1].toCharArray());
            else if (op[0].equals("2")) delete(op[1].toCharArray());
            else if (op[0].equals("3")) list.add(search(op[1].toCharArray()) ? "YES" : "NO");
            else list.add(prefixNumber(op[1].toCharArray()) + "");
        }
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        return res;
    } 
    
    static class TrieNode {
        char val;
        int preCount;
        int endCount;
        Map<Character, TrieNode> sons = new HashMap<>();
        
        public TrieNode(char val) {
            this.val = val;
        }
    }
    
    private TrieNode root;
    
    private void insert(char[] word) {
        TrieNode node = root;
        for (char item : word) {
            if (node.sons == null) node.sons = new HashMap<>();
            if (!node.sons.containsKey(item)) node.sons.put(item, new TrieNode(item));
            node = node.sons.get(item);
            node.preCount++;
        }
        node.endCount++;
    }
    
    private boolean search(char[] word) {
        TrieNode node = root;
        for (char item : word) {
            if (node.sons == null || !node.sons.containsKey(item)) return false;
            node = node.sons.get(item);
        }
        return node.endCount > 0;
    }
    
    private int prefixNumber(char[] word) {
        TrieNode node = root;
        for (char item : word) {
            if (node.sons == null || !node.sons.containsKey(item)) return 0;
            node = node.sons.get(item);
        }
        return node.preCount;
    }
    
    private void delete(char[] word) {
        TrieNode node = root;
        for (char item : word) {
            node = node.sons.get(item);
            node.preCount--;
        }
        node.endCount--;
    }
}

发表于 2021-02-18 14:50:45 回复(0)

Java

花落梦里

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
   public String[] trieU(String[][] operators) {
        //1:添加，2：删除都不输出
        HashMap<String, Integer> dict = new HashMap();
        ArrayList<String> res = new ArrayList();
        for (int i = 0; i < operators.length; i++) {
            String op = operators[i][0];
            String str = operators[i][1];
            if (op.equals("1")) {
                if (dict.containsKey(str))
                    dict.put(str, dict.get(str) + 1);
                else dict.put(str, 1);
            }
            else if (op.equals("2")) {//数据保证不会删除不存在的word
                if (dict.get(str) == 1) dict.remove(str);
                else dict.put(str, dict.get(str) - 1);
            }
            else if (op.equals("3")) {//查询是否存在
                if (dict.containsKey(str)) res.add("YES");

                else res.add("NO");
            }
            else if (op.equals("4")) {//以word为前缀的单词数目
                int count = 0;
                for (String key : dict.keySet()) {
                    if (key.startsWith(str))
                        count++;
                }
                res.add("" + count);
            }

        }

        int n = res.size();
        String[] res2 = new String[n];
        for (int i = 0;i < n; i++)
            res2[i] = res.get(i);
        return res2;
    }
}

发表于 2021-02-05 18:40:01 回复(1)

Java

六娃lw

构造前缀树，树节点中用数组存储26个字母对应的孩子节点，并用整形存储以该节点结尾的字符串的数量。

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        PrefixTree pt = new PrefixTree();
        List<String> list = new ArrayList<>(10);
        for(String[] oper: operators){
            switch(oper[0]){
                case "1":{pt.insert(oper[1]); break;}
                case "2":{pt.delete(oper[1]); break;}
                case "3":{
                    if(pt.search(oper[1])){
                        list.add("YES");
                    }else{
                        list.add("NO");
                    }
                    break;
                }
                case "4":{
                    list.add(new Integer(pt.prefixNumber(oper[1])).toString());
                }
            }
        }
        String[] res = new String[list.size()];
        for(int i = 0; i < list.size(); ++i){
            res[i] = list.get(i);
        }
        return res;
    }
    
    private class PrefixTree{
        private class Node{
            public Node[] children;
            public int count;
            public Node(){
                children = new Node[26];
                count = 0;
            }
        }
        
        private Node root = new Node();
        public void insert(String str){
            Node curr = this.root;
            for(int i = 0; i < str.length(); ++i){
                char ch = str.charAt(i);
                if(curr.children[ch - 'a'] == null){
                    Node next = new Node();
                    curr.children[ch - 'a'] = next;
                }
                curr = curr.children[ch - 'a'];
            }
            curr.count++;
        }
        public void delete(String str){
            Node curr = this.root;
            for(int i = 0; i < str.length(); ++i){
                char ch = str.charAt(i);
                curr = curr.children[ch - 'a'];
                if(curr == null){
                    return;
                }
            }
            curr.count = 0;
        }
        public boolean search(String str){
            Node curr = this.root;
            for(int i = 0; i < str.length(); ++i){
                char ch = str.charAt(i);
                curr = curr.children[ch - 'a'];
                if(curr == null){
                    return false;
                }
            }
            return curr.count != 0;
        }
        public int prefixNumber(String str){
            Node curr = this.root;
            for(int i = 0; i < str.length(); ++i){
                char ch = str.charAt(i);
                curr = curr.children[ch - 'a'];
                if(curr == null){
                    return 0;
                }
            }
            int[] cnt = {0};
            dfs(curr, cnt);
            return cnt[0];
        }
        
        private void dfs(Node node, int[] cnt){
            if(node == null){return;}
            cnt[0] += node.count;
            for(int i = 0; i < 26; ++i){
                dfs(node.children[i], cnt);
            }
        }
    }
    
}

发表于 2020-12-11 22:41:27 回复(0)

Java

范特西Fantasy

public class Solution {
    private TreeNode root;
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        if (operators == null || operators.length == 0 || operators[0].length == 0) return null;
        root = new TreeNode('/');
        List<String> list = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            switch(operators[i][0]) {
                case "1":
                    // 添加word
                    insert(operators[i][1]);
                    break;
                case "2":
                    // 删除word
                    delete(operators[i][1]);
                    break;
                case "3":
                    // 查询是否在字典中
                    list.add(find(operators[i][1]));
                    break;
                case "4":
                    list.add(String.valueOf(stat(operators[i][1])));
                    break;
                default:
            }
        }
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    void insert(String s) {
        if (s == null || s.length() == 0) return;
        char[] arr = s.toCharArray();
        TreeNode p = root;
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - 'a';
            if (p.children[index] == null) {
                TreeNode newNode = new TreeNode(arr[i]);
                p.children[index] = newNode;
            }
            p = p.children[index];
            p.path++;
        }
        p.isEndingChar = true;
    }

    void delete(String s) {
        if (s == null || s.length() == 0) return;
        char[] arr = s.toCharArray();
        TreeNode p = root;
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - 'a';
            if (p.children[index] == null) return;
            if (p.children[index].path-- == 0) {
                p.children[index] = null;
                return;
            }
            p = p.children[index];
        }
        p.isEndingChar = false;
    }

    int stat(String s) {
        if (s == null || s.length() == 0) return 0;
        char[] arr = s.toCharArray();
        TreeNode p = root;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) { 
            int index = arr[i] - 'a';
            if (p.children[index] == null) {
                return 0;
            }
            p = p.children[index];
        }
        return p.path;
    }

    String find(String s) {
        if (s == null || s.length() == 0) return "NO";
        char[] arr = s.toCharArray();
        TreeNode p = root;
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - 'a';
            if (p.children[index] == null) {
                return "NO";
            }
            p = p.children[index];
        }
        return p.isEndingChar?"YES":"NO";
    }

    class TreeNode {
        char val;
        TreeNode[] children;
        int path; // 以当前node为路径的单词数
        boolean isEndingChar = false;  // 是否是最后一个字符

        TreeNode(char val) {
            this.val = val;
            children = new TreeNode[26];
            path = 0;
        }
    }
}

发表于 2020-12-03 07:44:51 回复(0)

Java

callmejacky

😀

import java.util.*;


public class Solution {
    // 字典树的数据结构
    public static class Trie {
        public class TrieNode{
            public int path;
            public int end;
            public HashMap<Character, TrieNode> next;

            public TrieNode(){
                path = 0;
                end = 0;
                next = new HashMap<>();
            }
        }

        private TrieNode root;
        public Trie(){
            root = new TrieNode();
        }

        public void insert(String word){
            if(word == null || word.equals(""))  return ;
            TrieNode node = root;
            for(int i = 0; i<word.length(); i++){
                char ch = word.charAt(i);
                if(!node.next.containsKey(ch)) {
                    node.next.put(ch,new TrieNode());
                }
                node = node.next.get(ch);
                node.path++;
            }
            node.end++;
        }

        public boolean search(String word){
            if(word == null || word.equals("")) return false;
            TrieNode node = root;
            for(int i = 0; i<word.length(); i++){
                char ch = word.charAt(i);
                if(!node.next.containsKey(ch)) return false;
                node = node.next.get(ch);
            }
            if(node.end == 0) return false;
            return true;
        }
        public int startsWith(String word){
            if(word == null || word.equals("")) return 0;
            TrieNode node = root;
            for(int i = 0; i<word.length(); i++){
                char ch = word.charAt(i);
                if(!node.next.containsKey(ch)) return 0;
                node = node.next.get(ch);
            }
            return node.path;
        }
        public void delete(String word){
            if(word == null || word.equals("") || !search(word)) return ;
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if(--node.next.get(ch).path == 0){
                    node.next.remove(ch);
                    return;
                }
                node = node.next.get(ch);
            }
            node.end--;
        }
    }

    /**
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU(String[][] operators) {
        Trie root = new Trie();
        // write code here
        List<String> result = new ArrayList<String>();
        int m = operators.length;
        int n = operators[0].length;
        for (int i = 0; i < m; i++) {
            if (operators[i][0].equals("1")) {
                root.insert(operators[i][1]);
            } else if (operators[i][0].equals("2")) {
                root.delete(operators[i][1]);
            } else if (operators[i][0].equals("3")) {
                boolean flag = root.search(operators[i][1]);
                if (flag) {
                    result.add("YES");
                } else {
                    result.add("NO");
                }
            } else {
                int count = root.startsWith(operators[i][1]);
                result.add(count + "");
            }
        }
        String[] res = new String[result.size()];
        result.toArray(res);
        return res;
    }
}

发表于 2020-09-27 13:49:42 回复(0)

字典树的实现

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题