Trie - 211. Add and Search Word - Data structure design

ppxai

发布于 2020-09-23 17:30:19

2400

发布于 2020-09-23 17:30:19

211. Add and Search Word - Data structure design 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") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note: You may assume that all words are consist of lowercase letters a-z.

思路：

由于这一题的匹配是可以直接使用.代替任意字符，所以可以用一个map存下左右的输入字符串，然后用简单的单个字符的比较来做search，但是这里使用前缀树来做。

代码：

go：

const R = 26


type WordDictionary struct {
    Children [R]*WordDictionary
    Word bool
}


/** Initialize your data structure here. */
func Constructor() WordDictionary {
    return WordDictionary{}
}


/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string)  {
    cur := this
    for i := 0; i < len(word); i++ {
        c := rune(word[i])
        if cur.Children[c - 'a'] == nil {
            cur.Children[c - 'a'] = &WordDictionary{Children : [R]*WordDictionary{}, Word:false}
        }
        cur = cur.Children[c - 'a']
    }
    cur.Word = true
}


/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {
    return searchWord(word, this)
}

func searchWord(word string, node *WordDictionary) bool {
    for i := 0; i < len(word) && node != nil; i++ {
        c := rune(word[i])
        if c != '.' {
            node = node.Children[c - 'a']
        } else {
            temp := node
            for _, children := range temp.Children {
                node = children
                if searchWord(word[i+1:], node) {
                    return true
                }
            }
        }
    }
    return node != nil && node.Word
}


/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年08月26日，如有侵权请联系 cloudcommunity@tencent.com 删除

lowercase