211. Add and Search Word - Data structure design（python+cpp）（前缀树的升级版）-白红宇

211. Add and Search Word - Data structure design（python+cpp）（前缀树的升级版）

阅读量：3703 次

发布时间：2019-05-21

本文共 3687 字，大约阅读时间需要 12 分钟。

题目：

Design a data structure that supports the following two operations:
　void addWord(word)
　bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or …A . means it can represent any one letter.
Example:
addWord("bad") addWord("dad") addWord("mad") search("pad") -> falsesearch("bad") -> true search(".ad") -> true search("b..") -> true
Note: You may assume that all words are consist of lowercase letters
a-z.

解释：

注意，字母可以用.代替，要是在插入的时候做文章，那么整个Trie将会变得巨大无比，所以应该在search的时候做文章，所以在search()函数内，更新current指针就不太合适了，应该通过递归来判断。

python代码：

#与208. Implement Trie (Prefix Tree)类似from collections import defaultdictclass TrieNode(object):    def __init__(self):        self.children=defaultdict(TrieNode)        self.is_word=False        class WordDictionary(object):    def __init__(self):        """        Initialize your data structure here.        """        self.root=TrieNode()            def addWord(self, word):        """        Adds a word into the data structure.        :type word: str        :rtype: void        """        current=self.root        for letter in word:            current=current.children[letter]        current.is_word=True            def search(self, word):        """        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.        :type word: str        :rtype: bool        """        return self.searchFrom(self.root,word)            def searchFrom(self,root,word):        for i in range(len(word)):            letter=word[i]            if letter=='.':                #字典                for child in root.children:                    if self.searchFrom(root.children[child],word[i+1:]):                        return True                return False            elif letter not in root.children:                return False            else:                root=root.children[letter]        return root.is_word# Your WordDictionary object will be instantiated and called as such:# obj = WordDictionary()# obj.addWord(word)# param_2 = obj.search(word)

c++代码（速度还行）：

#includeusing namespace std;struct TrieNode{
       bool isWord;    map
    
      children;    TrieNode():isWord(false){
   }};class WordDictionary {
   public:    /** Initialize your data structure here. */    TrieNode* root;    WordDictionary() {
           root=new TrieNode();    }        /** Adds a word into the data structure. */    void addWord(string word) {
           TrieNode* current=root;        for (auto letter:word)        {
               if (!current->children.count(letter))                current->children[letter]=new TrieNode();            current=current->children[letter];        }        current->isWord=true;    }        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */    bool search(string word) {
           TrieNode* tmp=root;        return searchFrom(tmp,word);    }    bool searchFrom(TrieNode* root,string word)    {
           int n=word.size();        for (int i=0;i
     
      children)                {
                       if (searchFrom(child.second,word.substr(i+1,n-i-1)))                        return true;                     }                return false;            }            else if(!root->children.count(letter))                return false;            else                root=root->children[letter];                    }        return root->isWord;    }};/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * bool param_2 = obj.search(word); */

总结：

转载地址：http://dzmcn.baihongyu.com/

你可能感兴趣的文章