Don’t you know how to use dictionary trees?

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

instructions

Dictionary tree: Also known as word lookup tree, Trie tree, is a tree structure, hash tree variant. It is typically used to count, sort and save large numbers of strings (but not limited to strings), so it is often used for text word frequency statistics by search engine systems. Its advantages are that it reduces query time by using the common prefix of strings, minimizes unnecessary string comparisons, and improves query efficiency over hash trees.

Dictionary tree template:

public class WordTree {
    /**
     * 下一级节点
     */
    private WordTree[] next;
    /** * word end identifier */
    private boolean isEnd;

    public WordTree(a) {
        this.next = new WordTree[26];
    }

    /** * add word */
    public void addWrod(String word){
        WordTree wordTree = this;
        for(char w : word.toCharArray()){
            // Create a sub-character node
            if (null == wordTree.next[w - 'a']){
                wordTree.next[w - 'a'] = new WordTree();
            }
            wordTree = wordTree.next[w - 'a'];
        }
        // The new word is added
        wordTree.isEnd = true;
    }
    
    /** * find the word */
    public boolean search(String word){
        WordTree wordTree = this;
        // Traverses the lower character node to see if the character exists
        for(char w : word.toCharArray()){
            if (null == wordTree.next[w - 'a']) {return false;
            }
            wordTree = wordTree.next[w - 'a'];
        }
        
        // Return the result
        returnwordTree.isEnd; }}Copy the code

The title

211. Add and search words – Data structure design

You can design a data structure that supports adding new words and finding out if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary()Initialize the dictionary object
• void addWord(word) 将 wordAdd to the data structure, which can then be matched
• bool search(word)If the data structure contains strings andwordMatches, returntrue; Otherwise, returnfalse 。wordMay contain some'. ', each.Can represent any letter.

The sample

Input:  ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[], [" bad "], [" dad "], [" mad "], [" pad "], [" bad "], [" AD "], [" b... "]] output: [null, null, null, null, false, true, true, true) :  WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.." ); // return TrueCopy the code

prompt

• 1 <= word.length <= 500
• addWordIn thewordConsists of lowercase English letters
• searchIn thewordConsists of ‘.’ or lowercase letters
• Most call50000 次 addWord 和 search

Their thinking

Looking at words and looking up strings, it’s easy to think of a dictionary tree. Slightly different, in the search for a string, we need to do a fuzzy query for ‘.’, which modifies the conventional dictionary tree search logic and uses a search algorithm to determine if the string exists.

Code implementation

class WordDictionary {
    /**
     * 下一级节点
     */
    private WordDictionary[] next;
    /** * word end identifier */
    private boolean isEnd;

    public WordDictionary(a) {
        this.next = new WordDictionary[26];
    }
    
    /** * add word */
    public void addWord(String word) {
        WordDictionary wordDictionary = this;
        for(char w : word.toCharArray()){
            if(null == wordDictionary.next[w - 'a']){
                wordDictionary.next[w - 'a'] = new WordDictionary();
            }
            wordDictionary = wordDictionary.next[w - 'a'];
        }
        wordDictionary.isEnd = true;
    }
    
    /** * find the word */
    public boolean search(String word) {
        // As this problem requires fuzzy search, DFS is used here to judge
        return searchAll(word.toCharArray(), 0.this);
    }

    / * * *@paramWord string *@paramThe index index *@paramWords node * /
    public boolean searchAll(char[] word, int index, WordDictionary words){
        for(int i = index; i < word.length; ++i){
            // Fuzzy search requires traversing all existing child nodes
            if('. ' == word[i]){
                boolean res = false;
                for(WordDictionary w : words.next){
                    if(w ! =null && !res){
                        res |= searchAll(word, i + 1, w); }}return res;
            }
            // The child node does not exist
            if(words.next[word[i] - 'a'] = =null) {return false;
            }else{
                // If the byte dot exists, continue searching down
                words = words.next[word[i] - 'a']; }}// Return the result
        returnwords.isEnd; }}Copy the code

Complexity analysis

• Time complexity:addWordOperation for
  $O(L)$.serachOperation for
  $O(LM)$.
• Space complexity: O(LM)O(LM)O(LM).
• LIs the string length,MOccupies space for child nodes. In this case, is26

Similar to the topic

212. Word Search II: leetcode-cn.com/problems/wo…

208. Implement Trie (prefix tree) : leetcode-cn.com/problems/im…

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!