设计添加和搜索单词数据结构：Leetcode 211

Question

我目前正在尝试解决leetcode上的问题添加和搜索单词数据结构。问题如下：

设计一个支持添加新单词和查找 if 的数据结构 字符串与任何先前添加的字符串相匹配。

实现WordDictionary类：

WordDictionary()

初始化对象。

void addWord(word)

将

word

添加到数据结构中，稍后可以进行匹配。

bool search(word)

如果数据结构中有任何字符串匹配，则返回

true

word

或

false

否则。单词可能包含点

.

其中点可以是 与任何字母匹配。

我的代码：

class WordDictionary(object):

    def __init__(self):
        self.map = {}

    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        current = self.map
        for i in word:
            if i in current:
                current = current[i]
            else:
                current[i] = {}
                current = current[i]
        current['end'] = {}
        
        return
        

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        current = self.map
        for i in word:
            if i in current:
                current = current[i]
            elif i == '.':
                current = {key: value for d in current.values() for key, value in d.items()}
            else:
                return False
        if 'end' in current:
            return True
        return False

该解决方案似乎对大多数情况都有效，但我在 测试用例 16 中遇到了错误，它没有给出正确的结果。测试用例 16 的长度使得查明错误发生的位置特别具有挑战性。我需要一些指导来追踪并修复这个逻辑错误。你能帮忙解决这个问题吗？

Answer 1

设计数据结构

这是您实现的一个有趣的结构。 抱歉，我不知道它是如何与测试 16 发生冲突的。

        current['end'] = {}

如果您存储 N 个单词，则需要 N

dict

分配。

考虑简单地存储指向同一个旧单例的指针， 所以我们少一点 malloc() ：

        current['end'] = None

排列

排序的数据结构往往有利于通配符匹配。 问题是

search('a.ple')

可能会迫使我们 扫描所有以“a”开头的条目，其中“a”是常用字母。 或者更糟糕的是，

search('.pple')

可能会强制对所有内容进行 O(N) 线性扫描。 假设我们不知道 etaoin shrdlu 字母频率， 并且无法在比赛环境中测量它们。

解决这个问题的一种方法是存储所有排列：

from sortedcontainers import SortedDict

d = SortedDict()
add(d, 'apple', 'apple')
add(d, 'pplea', 'apple')
add(d, 'pleap', 'apple')
add(d, 'leapp', 'apple')
add(d, 'eappl', 'apple')

def add(d: SortedDict, k: str, v: str) -> None:
    if k not in d:
        # The set deals with the ambiguity of anagrams,
        # e.g. {eat, ate, tea}
        d[k] = set()
    d[k].add(v)

现在当我们遇到一两个通配符时 search() 查询中的字符，这是一个问题 识别最长的一段确定字母。 所以对于

".pp.e"

我们会扫描 d.irange(“pp”,“pq”) 寻找位于正确位置且带有

"e"

的按键。 对于像

"a..le"

这样的查询，我们会扫描

d.irange("lea", "leb")

。

您无法为比赛安装 pip 安装包， 但你当然可以实现足够的二分搜索代码 支持这个。

字谜

让我们更努力地依靠打乱的字母顺序。

假设我们想要找到查询词的字谜词。 标准解决方案是对字母进行排序并存储。 所以

''.join(sorted('apple'))

->

'aelpp'

此方案的灾难性查询将是

'.ppl.'

。 这似乎让我们回到与字长成正比的存储。 让我们尝试存储第二个副本，相反的排序：

'pplea'

。 现在我们可以 zip() 增加这两个迭代器：

• d.irange('lpp', 'lpq')
• d.irange('ppl', 'ppm')

无论哪一个先产生匹配，都将获胜，从而终止循环。 这个方案有一个很好的对称性：当添加单词时和查询时 无论我们收到多少个字母，我们总是可以按字母顺序排列。

考虑一个没有重复字符的示例。

• 'fruit'

  -->

  'firtu'

• 'fruit'

  -->

  'utrif'

此方案的灾难性查询将是

'.r.it'

因此，也许添加第三个条目，从中间排列（例如

'rtufi'

）， 今天就到此为止了吗？ 选择三个条目利用了以下事实： 对手仅限于两个通配符。

我一直在努力避免存储条目数量 这是字长的二次方，因为 15 个字符是 最大字长，15 × 14 = 210 是一个很大的数字。 也许存储所有可能的单通配符查询的条目 这是正确的权衡。

对于长单词，通配符会淘汰

'm'

或

'n'

似乎 无趣；仅靠近

'a'

的前几个字母， 最后几个靠近

'z'

的字母有很大的力量 破坏查询。 如果例如

'b'

和

'c'

被通配符淘汰， 那么反向副本将拯救我们。 同样，如果

's'

和

'u'

被淘汰， 正向副本肯定可以进行有效的查询。 因此，条目数量可以随字长呈亚线性增长。

字母数

哦，添加和查询时还知道一件事： 字母数。 所以我们字典的第一个索引应该是

word_len

， 接下来是

sorted_letters

或其他：

d[5]['firtu'].add('fruit')