[leetcode] 第三十四部分(211)

211-Add and Search Word – Data structure design

问题描述

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

void addWord(word)
bool search(word)

search(word) 可以检索一个字面上的词语或者只包含字符a-z或者. 的正则表达字符串. . 可以表示任意字符.

示例:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

注意:
可以假设所有词语只由小写字符a-z组成.

解题思路

看到这种类型的题目, 最直观的想法是 使用一个字典的方式来存储, 然后进行检索… 不过很明显, 这无法支持.匹配, 时间复杂度会比较高.

然后最简单直接的就是想到用树的方法解决, 其实 这是一个典型的 字典树的问题.

xxx

上图就是一个典型的字典树, 有如下特征:

  • 根节点不包含字符, 除了根节点外的每个子节点都包含一个字符
  • 从根节点到某个最终节点, 路径上出现的所有字符按照顺序连起来, 就是该节点对应的字符串
  • 每个节点的所有子节点包含的字符互不相同

需要定义一个Node对象来存储孩子节点, 以及一个标志来标识是否已经到了最后一个字母. 而在匹配的时候, 需要具体区分一下. 可以等价于所有字符, 因此, 可能有多个方向, 这里需要使用一个list来存储接下来需要匹配的节点.

代码

class Node(object):

    def __init__(self):
        self.children = dict()
        self.is_word = False

class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: None
        """
        cur = self.root
        for w in word:
            if w not in cur.children: 
                cur.children[w] = Node()
            cur = cur.children[w]
        cur.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
        """
        # 逐个遍历
        cur_list = [self.root]
        for i, w in enumerate(word):
            new_list = []
            for node in cur_list:
                for key, value in node.children.items():
                    # 如果当前字符匹配
                    if "." == w or key == w:
                        if i == len(word) -1  and value.is_word:
                            return True
                        new_list.append(value)
            cur_list = new_list
        return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
打赏

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注