数据结构算法提高之LeetCode刷题Java数据结构和算法

数据结构之字典树Trie

2019-08-11  本文已影响72人  Ice_spring

字典树Trie

字典树也叫前缀树,是一种在字符串查找,前缀匹配等问题广泛应用的算法,为什么使用字典树呢?我们都知道如果对于一个存储有n个条目的数据集做查询,线性结构的时间复杂度是O(n),这是相当恐怖的,改进的基于红黑树的查询时间复杂度是O(logn),虽然已经好很多,但是当n非常大时,这个时间复杂度还是不能接受的。而字典树能做到查询的时间复杂度和数据集存储的数目n无关,而仅和被查询的字符串长度有关,所以它在查找时只有O(1)的时间复杂度。这是怎么做到的呢,其实很简单,下图是某存储英文的字典树的结构:

Trie

该树中存储了英语单词bed,beat,win,wind,yes,如果要查询某个单词,比如wind,只需要先找到w,再找到i、n、d即可。可见对每个单词的查找只需要查找单词长度次,而且每次查找只需查找26次之内(即便算上大写也在52次之内)。
Trie数据结构设计要点:


字典树的实现
首先考虑节点结构,并假设这里的节点仅存储小写英文单词,故每个节点下应该有26个分支(实际如何存储根据具体情境):

class Node{
    char c;
    Node next[26];//指向下一个节点
}

不过由于在寻找下一个节点时,我们实际上已经知道了要找哪个,故可以将当前节点和和其指向的节点存储为一个整体(相当于存储是在边上),考虑到Java中TreeMap中键值对中一个键对应的值可以添加多个,这些值组成一个keySet,故节点设计为:

class Node{
    boolean isWord;
    Map<char,Node> next;
}

其中isWord用于标识单词结尾,从而Trie类:

import java.util.TreeMap;
public class Trie {//不需要泛型,这里仅解决字符串类问题
    private class Node{//Trie的节点类
        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中添加新单词(字符串)
    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)//如果映射中没有包含到c的映射
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if (!cur.isWord) {//首先检查该单词是否已经存在
            cur.isWord = true;
            //此时来到了当前添加单词的最后节点,但不一定是叶子节点,因为可能是别的单词前缀
            size++;
        }
    }//作业:使用递归写法完成添加操作

    public boolean contains(String word){
        //查询单词word是否在Trie中
        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也是一个集合
    public boolean isPrefix(String prefix){
        //查询Trie中是否有单词以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;//和查询单词操作类似,不过无需检查是否包含单词
        //作业:BSTSet中查询前缀
    }
}

可以看到,Trie类的实现我们借助了TreeMap等底层数据结构,这正是数据结构的魅力,就像乐高积木一样,由一些基础的木块一步步搭建出美丽的艺术品。

Trie的应用——LeetCode207、211

LeetCode207不再介绍,就是设计一个字典树类,支持添加和查找操作,我们实现的类修改下类名即可。
LeetCode211

LeetCode211

这个题目其实和Trie类要完成的工作类似,不过加入了一些更灵活的条件(简易正则表达式),只需对我们的Trie类做小部分修改即可:

import java.util.TreeMap;
class WordDictionary {
    private class Node{//Trie的节点类
        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();
    }
    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)//如果映射中没有包含到c的映射
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if (!cur.isWord) //首先检查该单词是否已经存在
            cur.isWord = true;
    }
    public boolean search(String word) {
        return match(root, word,0);
    }
    private boolean match(Node node, String word, int index) {
        //从index处开始匹配
        if (index == word.length())
            return node.isWord;//递归终止条件,word匹配完毕,若为true则返回匹配成功,false匹配失败
        char c = word.charAt(index);
        if (c == '.') {
            for (char nextChar : node.next.keySet()) {//是.则遍历所有字母
                if (match(node.next.get(nextChar), word, index + 1))
                    return true;
            }
            return false;
        } else {
            if (node.next.get(c) == null)
                return false;
            return match(node.next.get(c), word, index + 1);//继续匹配后面的部分
        }
    }
}

可以发现,我们只对查询函数做了比较大的改动,而查询主要是基于递归实现的。
提交,获得通过!

上一篇下一篇

猜你喜欢

热点阅读