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

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,对于每一个不是.这样的字母,我们都将使用和之前查找的操作一样去找到当前的节点的下一个字母所映射的节点。
数据结构笔记总结(9.5)Trie字典树和简单的模式匹配
比如说起始是从根节点开始的,第一个字母是d,于是我们就来到了d,之后由于下一个字母是.,换句话说可以是任意的字符,d的next所指向的所有的字符都可以匹配这个点,此时我们要做的就是一次搜索,必须遍历所有的可能,也就是遍历d这个节点中存储的next下的所有的节点,看从这些节点开始是否可以匹配后面的,整体的思路就是这样的。数据结构笔记总结(9.5)Trie字典树和简单的模式匹配
具体遍历的方式是什么?由于我们是在一个树的结构中,遍历当然是之前讲的前中后序遍历,其实本质就是一个递归遍历的过程,所以对于这个问题写一个递归的算法是比较好解决的。

具体代码实现

import java.util.TreeMap;

public class WordDictionary {

    private class Node{

        public boolean isWord;
        public TreeMap 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;
        }
    }
}

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(9.5)Trie字典树和简单的模式匹配
分享到:
赞(0)

评论抢沙发

评论前必须登录!