前缀树/Trie

原创
2020/03/10 10:07
阅读数 13

概述

Trie 也加字典树,它是一个树形结构。它主要用于处理字符串匹配的数据结构。此外Trie 树也称 前缀树(PrfixTree),主要判断字符串是否是以某个子串开头。

用途

解决在一组字符串集合中快速查找某个字符串的问题。

性质

每个节点至少包含两个基本属性

child:数组或者集合,罗列出每个分支当中包含的所有字符

isEnd 布尔值表示该节点是否为某个字符串的结尾

操作

创建

遍历一遍输入的字符串,对每个字符串的字符进行遍历

从前缀树的根节点开始,将每个字符加入到节点的children字符集当中

如果字符集已经包含了这个字符,跳过

如果当前字符是字符串的最后一个,把当前节点的isEnd标记为真


import java.util.TreeMap;

public class Trie {

    private class Node{
        public boolean isWord;
        public TreeMap<Character,Node> next;

        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }
    }
    private Node root;
    private int size;

    public Trie(){
        root = new Node(false);
        size = 0;
    }

    public void add(String word){
        Node currNode = root;
        for(int i = 0;i<word.length();i++){
            char c = word.charAt(i);
            if (currNode.next.get(c) ==null){
                currNode.next.put(c,new Node(false));
            }
            currNode = currNode.next.get(c);
        }
        if (!currNode.isWord){
            currNode.isWord = true;
            size++;
        }
    }



}


一个 int 即可存储 26 个字母

搜索

Go语言中字符串前缀判断



本文同步分享在 博客“羊羽”(other)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享

作者的其它热门文章

加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部