数据结构之Trie字典树

什么是Trie

Trie字典树，查询每个条目的时间复杂度和字典一共有多少个条目无关！时间复杂度为O(w)，w为查询单词的长度，每个节点有若干个指向下个节点的指针，考虑不同的语言，不同的情景。如下图，每个节点有26个指向下个节点的指针

Trie字典树的添加

package trie;
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<>();
        }
        public Node()
        {
            this(false);
        }

    }
    private Node root;
    private int size;

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

    //获得Trie中存储的单词数量
    public int getSize()
    {
        return size;
    }
    //向Trie中添加一个新的单词word
    public void add(String word)
    {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null)	//如果cur.next不包含c
                cur.next.put(c,new Node());	//就将cur.next里put进c
            cur=cur.next.get(c);//反之，包含有c，那么直接走到cur.next.get(c)这个节点
        }
        if(!cur.isWord)//判断，cur以前并不表示其他单词是false
        {
            cur.isWord = true;//另cur为true
            size++;
        }
    }
}

查询

//查询单词word是否在Trie中
   public boolean contains(String word)
   {
       Node cur = root;
       for (int i = 0; i < word.length();i++)
       {
           char c = word.charAt(i);
           if(cur.next.get(c) == null)
               return false;
           cur = cur.next.get(c);
       }
       return cur.isWord;
   }

前缀查询

//查询是否在Trie中有单词以prefix为前缀
    public boolean isPrefix(String prefix)
    {
        Node cur = root;
        for (int i = 0; i < prefix.length();i++)
        {
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }
        return true;
    }

实现Trie（前缀树 leecode）

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

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<>();
        }
        public Node()
        {
            this(false);
        }

    }
    private Node root;

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

    //向Trie中添加一个新的单词word
    public void insert(String word)
    {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c,new Node());
            cur=cur.next.get(c);
        }
        if(!cur.isWord)
        {
            cur.isWord = true;
        }

    }
    //查询单词word是否在Trie中
    public boolean search(String word)
    {
        Node cur = root;
        for (int i = 0; i < word.length();i++)
        {
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }
    //查询是否在Trie中有单词以prefix为前缀
    public boolean startsWith(String isprefix)
    {
        Node cur = root;
        for (int i = 0; i < isprefix.length();i++)
        {
            char c = isprefix.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }
        return true;
    }

}

添加与搜索单词（leecode）

设计一个支持以下两种操作的数据结构：void addWord(word) bool search(word)，search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

import java.util.TreeMap;

class WordDictionary {

    private class Node
    {
        public boolean isWord;
        public TreeMap<Character,Node> next;
        public Node(boolean isWord)
        {
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        public Node()
        {
            this(false);
        }
    }
    private Node root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c,new Node());
            cur=cur.next.get(c);
        }
        cur.isWord = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return match(root,word,0);
    }
    private boolean match(Node node,String word,int index)
    {
        if(index == word.length())
            return node.isWord;
        char c = word.charAt(index);
        if(c != '.')
        {
            if(node.next.get(c) == null)
                return false;
            return match(node.next.get(c),word,index+1);
        }
        else
        {
            for(char nextChar:node.next.keySet())
                if(match(node.next.get(nextChar),word,index+1))
                    return true;
                return false;
        }
    }
}