NC124 字典树的实现

字典树的实现

https://www.nowcoder.com/practice/a55a584bc0ca4a83a272680174be113b?tpId=196&&tqId=37151&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking

import java.util.*;


public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        List<String> res = new ArrayList<>();
        Trie tree = new Trie();
        for(int i = 0;i < operators.length;++i){
            switch(operators[i][0]){
                    // 插入
                case "1":
                    tree.insert(operators[i][1]);
                    break;
                    // 删除
                case "2":
                    tree.delete(operators[i][1]);
                    break;
                    // 查找单词
                case "3":
                    res.add(tree.search(operators[i][1]));
                    break;
                    // 查找前缀
                case "4":
                    res.add(String.valueOf(tree.prefixNumber(operators[i][1])));
                    break;
            }
        }
        String[] ans = new String[res.size()];
        for (int i = 0;i < ans.length;++i){
            ans[i] = res.get(i);
      }
      return ans;
    }
    class Trie {
        class TrieNode{
            int end;
            int prefix;
            char ch;
            TrieNode[] next = new TrieNode[26];
            public TrieNode (){
                end = 0;
                prefix = 0;
            }
        }

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

        public void insert(String word){
            TrieNode p = root;
            for(int i=0;i<word.length();i++){
                int index = word.charAt(i) - 'a';
                if(p.next[index] == null) p.next[index] = new TrieNode();
                p.prefix++;
                p = p.next[index];
                p.ch = word.charAt(i);
            }// 结尾处理
            p.prefix++;
            p.end ++;
        }

        public void delete(String word){
            TrieNode p = root;
            for(int i=0;i<word.length();i++){
                int index = word.charAt(i) - 'a';
                TrieNode cur = p.next[index];
                cur.prefix--;
                if(cur.prefix == 0){ // 空了直接删除后续节点 break
                    p.next[index] = null;
                    break;
                }
                p = p.next[index];
            }

        }
        public String search(String word){
            TrieNode p = root;
            TrieNode cur = null;
            int i=0;
            for(;i<word.length();i++){
                int index = word.charAt(i) - 'a';
                cur = p.next[index];
                // 判断的顺序也很重要 先判断是否为空 否则会报错
                if(p.next[index] != null && cur.prefix != 0 ) p = p.next[index];
                else break;
            }
            if(i == word.length() && cur.end != 0 ) return "YES";
            else return "NO";
        }

        public int prefixNumber(String pre){
            TrieNode p = root;
            TrieNode cur = null;
            int i = 0;
            for(;i<pre.length();i++){
                int index = pre.charAt(i) - 'a';
                cur = p.next[index];
                if(p.next[index] != null && cur.prefix != 0 ) p = p.next[index];
                else break;
            }
            if(i == pre.length() ) return p.prefix;
            else return 0;

        }
    }
}
全部评论

相关推荐

07-21 18:43
门头沟学院 Java
是暑期都招满了吗
ANEOY:今年感觉真是后端地狱级难度了,从暑期就是这样,前端需求非常大
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发
点赞 评论 收藏
分享
07-25 10:31
门头沟学院 Java
求问各位大佬,笔试都考点啥
投递科大讯飞等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务