算法记录

LeetCode 题目：

   请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

  实现词典类 WordDictionary：

WordDictionary() 初始化词典对象；

void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配；

bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true、否则，返回false；

word中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

说明

一、题目

输入：["WordDictionary","addWord","addWord","addWord","search","search","search","search"][[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]输出：[null,null,null,null,false,true,true,true]

二、分析

题目分析，典型的字典树应用，其中还存在有模糊查询的应用。

如果对于字典树还不太明白的可以看一下这篇博文 字典树

class WordDictionary {    private Node tree;    class Node {        Node[] next;        boolean flag;        public Node() {            next = new Node[26];            flag = false;        }        public void insert(String word) {            Node temp = this;            for(char c : word.toCharArray()) {                if(temp.next[c - 'a'] == null) temp.next[c - 'a'] = new Node();                temp = temp.next[c - 'a'];            }            temp.flag = true;        }        public boolean search(String word) {            Node temp = this;            for(int j = 0; j < word.length(); j++) {                if(!Character.isLetter(word.charAt(j))) {                    boolean flag = false;                    for(int i = 0; i < 26 && !flag; i++) {                        if(temp.next[i] == null) continue;                        flag |= temp.next[i].search(word.substring(j + 1, word.length()));                    }                    return flag;                }                if(temp.next[word.charAt(j) - 'a'] == null) return false;                temp = temp.next[word.charAt(j) - 'a'];            }            return temp.flag;        }    }    public WordDictionary() {        tree = new Node();    }    public void addWord(String word) {        tree.insert(word);    }    public boolean search(String word) {        return tree.search(word);    }}

<hr style=" border:solid; width:100px; height:1px;" color=#000000 size=1">

总结

字典树的应用。

原文;https://juejin.cn/post/7100823089717444639