题目

为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句（最少包含一个字母，以特殊字符 # 结尾）。除 # 以外用户输入的每个字符，返回历史中热度前三并以当前输入部分为前缀的句子。下面是详细规则：

一条句子的热度定义为历史上用户输入这个句子的总次数。
返回前三的句子需要按照热度从高到低排序（第一个是最热门的）。如果有多条热度相同的句子，请按照 ASCII 码的顺序输出（ASCII 码越小排名越前）。
如果满足条件的句子个数少于 3，将它们全部输出。
如果输入了特殊字符，意味着句子结束了，请返回一个空集合。

你的工作是 实现以下功能：

构造函数：

AutocompleteSystem(String[] sentences, int[] times): 这是构造函数，输入的是历史数据。Sentences 是之前输入过的所有句子，Times 是每条句子输入的次数，你的系统需要记录这些历史信息。

现在，用户输入一条新的句子，下面的函数会提供用户输入的下一个字符：

List<String> input(char c): 其中 c 是用户输入的下一个字符。字符只会是小写英文字母（a 到 z ），空格（’ ‘）和特殊字符（#）。输出历史热度前三的具有相同前缀的句子。

样例：

操作 ： AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
系统记录下所有的句子和出现的次数：
"i love you" : 5 次
"island" : 3 次
"ironman" : 2 次
"i love leetcode" : 2 次

现在，用户开始新的键入：

输入 ： input('i')
输出 ： ["i love you", "island", "i love leetcode"]
解释 ：
有四个句子含有前缀 "i"。其中 "ironman" 和 "i love leetcode" 有相同的热度，
由于 ' ' 的 ASCII 码是 32 而 'r' 的 ASCII 码是 114，
所以 "i love leetcode" 在 "ironman" 前面。同时我们只输出前三的句子，所以 "ironman" 被舍弃。

输入 ： input(' ')
输出 ： ["i love you","i love leetcode"]
解释:
只有两个句子含有前缀 "i "。

输入 ： input('a')
输出 ： []
解释 ：
没有句子有前缀 "i a"。

输入 ： input('#')
输出 ： []
解释 ：
用户输入结束，"i a" 被存到系统中，后面的输入被认为是下一次搜索。

注释：

输入的句子以字母开头，以 # 结尾，两个字母之间最多只会出现一个空格。
即将搜索的句子总数不会超过 100。每条句子的长度（包括已经搜索的和即将搜索的）也不会超过 100。
即使只有一个字母，输出的时候请使用双引号而不是单引号。

方案一（trie树）

class AutocompleteSystem:

    def __init__(self, sentences: List[str], times: List[int]):
        self.sentence = '' # 本次输入的句子
        self.trie = {} # trie 树
        for i, sentence in enumerate(sentences):
            node = self.trie
            for ch in sentence:
                if ch not in node:
                    node[ch] = {}
                node = node[ch]
            node['end'] = True
            node['count'] = times[i]

    def _addSentenceToTrie(self):
        node = self.trie
        for ch in self.sentence:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node['end'] = True
        if 'count' in node:
            node['count'] += 1
        else:
            node['count'] = 1

    def input(self, c: str) -> List[str]:
        if c != "#":
            self.sentence += c
        else:
            self._addSentenceToTrie()
            self.sentence = ''
            return []

        sentences = self._startsWith()
        return self._getFrequenceSentences(sentences)

    def _getFrequenceSentences(self, sentences, top=3):
        '''
        @param:
            sentences: [(count, str)]
        '''
        sentences.sort(key=lambda sentences: sentences[1])
        sentences.sort(key=lambda sentences: sentences[0], reverse=True)
        return [s for count, s in sentences[:top]]


    def _startsWith(self):
        node = self.trie
        for ch in self.sentence:
            if ch not in node:
                return []
            node = node[ch]
        return self._getAllWords(node, self.sentence)

    def _getAllWords(self, node, prefix):
        ret = []
        for key in node:
            if key == "count":
                continue
            if key == "end":
                ret.append((node['count'], prefix))
                continue
            ret.extend(self._getAllWords(node[key], prefix + key))

        return ret

# Your AutocompleteSystem object will be instantiated and called as such:
# obj = AutocompleteSystem(sentences, times)
# param_1 = obj.input(c)

优化点1：每次调用 input 可以保存本次输入查询到的节点，当下次 input 输入的字符不是 # 时，可以直接从该节点向前查询。

优化后方案

class AutocompleteSystem:

    def __init__(self, sentences: [str], times: [int]):
        self.sentence = '' # 本次输入的句子
        self.trie = {} # trie 树
        self.last_trie_node = None # 上次查询到的 trie 树节点
        self.stop = False # 是否终止在树中查询，如果前面的输入已经返回 []，则后续输入的内容如果不是 `#` 可直接返回
        for i, sentence in enumerate(sentences):
            node = self.trie
            for ch in sentence:
                if ch not in node:
                    node[ch] = {}
                node = node[ch]
            node['end'] = True
            node['count'] = times[i]

    def _addSentenceToTrie(self):
        node = self.trie
        for ch in self.sentence:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node['end'] = True
        if 'count' in node:
            node['count'] += 1
        else:
            node['count'] = 1

    def input(self, c: str) -> [str]:
        if c == "#":
            self._addSentenceToTrie()
            self.sentence = ''
            self.last_trie_node = None
            self.stop = False
            return []

        self.sentence += c

        if self.stop:
            return []
        sentences = self._startsWith(c)
        return self._getFrequenceSentences(sentences)

    def _getFrequenceSentences(self, sentences, top=3):
        '''
        @param:
            sentences: [(count, str)]
        '''
        sentences.sort(key=lambda sentences: sentences[1])
        sentences.sort(key=lambda sentences: sentences[0], reverse=True)
        return [s for count, s in sentences[:top]]


    def _startsWith(self, ch):
        if not self.last_trie_node: # 第一次查询
            self.last_trie_node = self.trie
        if ch not in self.last_trie_node:
            self.stop = True
            return []
        self.last_trie_node = self.last_trie_node[ch]
        return self._getAllWords(self.last_trie_node, self.sentence)

    def _getAllWords(self, node, prefix):
        ret = []
        for key in node:
            if key == "count":
                continue
            if key == "end":
                ret.append((node['count'], prefix))
                continue
            ret.extend(self._getAllWords(node[key], prefix + key))

        return ret

原文

https://leetcode-cn.com/explore/learn/card/trie/167/practical-application-i/649/
https://leetcode-cn.com/problems/design-search-autocomplete-system/solution/she-ji-sou-suo-zi-dong-bu-quan-xi-tong-by-leetcode/

算法（leetcode）

设计搜索自动补全系统

题目

方案一（trie树）

原文