[LeetCode]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.

For 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.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

题目大意:

设计一个数据结构支持下列两种操作:

void addWord(word)
bool search(word)

search(word)可以搜索一个普通字符串或者一个只包含字母a-z或者.的正则表达式。符号.代表任意单个字母。

测试用例见题目描述。

注意:
你可以假设所有的单词只包含小写字母a-z

提示:
完成此题目之前,最好先做Implement Trie (Prefix Tree)

解题思路:

字典树(Trie),通配符.可以用枚举实现。

Python代码:

class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.childs = dict()
        self.isWord = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
        node = self.root
        for letter in word:
            child = node.childs.get(letter)
            if child is None:
                child = TrieNode()
                node.childs[letter] = child
            node = child
        node.isWord = True

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
        return self.find(self.root, word)
    
    def find(self, node, word):
        if word == '':
            return node.isWord
        if word[0] == '.':
            for x in node.childs:
                if self.find(node.childs[x], word[1:]):
                    return True
        else:
            child = node.childs.get(word[0])
            if child:
                return self.find(child, word[1:])
        return False

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")

 

本文链接:http://bookshadow.com/weblog/2015/05/16/leetcode-add-and-search-word-data-structure-design/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论