• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(9.5)Trie字典树和简单的模式匹配

极客笔记 Geekerstar 11个月前 (05-20) 372次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

211. 添加与搜索单词 – 数据结构设计

设计一个支持以下两种操作的数据结构:

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

示例:

addWord(“bad”)
addWord(“dad”)
addWord(“mad”)
search(“pad”) -> false
search(“bad”) -> true
search(“.ad”) -> true
search(“b..”) -> true

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

解题模板:

class WordDictionary {

    /** Initialize your data structure here. */
    public WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        
    }
    
    /** 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) {
        
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

Trie字典树和简单的模式匹配

假设当前的Trie是这样一种情况,我们要Search的字符串是d..r,对于每一个不是.这样的字母,我们都将使用和之前查找的操作一样去找到当前的节点的下一个字母所映射的节点。

比如说起始是从根节点开始的,第一个字母是d,于是我们就来到了d,之后由于下一个字母是.,换句话说可以是任意的字符,d的next所指向的所有的字符都可以匹配这个点,此时我们要做的就是一次搜索,必须遍历所有的可能,也就是遍历d这个节点中存储的next下的所有的节点,看从这些节点开始是否可以匹配后面的,整体的思路就是这样的。
具体遍历的方式是什么?由于我们是在一个树的结构中,遍历当然是之前讲的前中后序遍历,其实本质就是一个递归遍历的过程,所以对于这个问题写一个递归的算法是比较好解决的。

具体代码实现

import java.util.TreeMap;

public 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;
        }
    }
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(9.5)Trie字典树和简单的模式匹配
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00