<分区>
缩写是一串字母数字字符。数字代表要跳过的字母数，例如 i18n 是国际化的缩写。 inter15 和 20 也是如此。假设您有一个单词字典，在字典中找到与给定缩写匹配的所有单词的最快方法是什么？您可以为字典使用您喜欢的任何数据结构，但查找匹配词的算法必须优于 O(n)，其中 n 是字典中的词数。
<分区>
缩写是一串字母数字字符。数字代表要跳过的字母数，例如 i18n 是国际化的缩写。 inter15 和 20 也是如此。假设您有一个单词字典，在字典中找到与给定缩写匹配的所有单词的最快方法是什么？您可以为字典使用您喜欢的任何数据结构，但查找匹配词的算法必须优于 O(n)，其中 n 是字典中的词数。
最佳答案
所以你有一个查询是 prefix - count - suffix。有几种方法可以解决这个问题。
如果前缀永远不会为空，那么您可以构建一个前缀树(它只是一个 trie)，并查询所有以该前缀开头的单词，过滤那些具有请求的长度和后缀的单词。
你可以通过构建一个 generalized suffix tree 来做同样的事情.
或者，由于前缀或后缀可以为空，您可以构建一个前缀树和一个后缀树。查询两者，过滤长度，并合并结果。
你可以想象构建一个单一的前缀-后缀树。数据结构会比拥有两棵独立的树更复杂，但它需要的内存更少。
我记得(已经有好几年了)，您可以使用有向无环词图 (DAWG) 完成所有这些以及更多(搜索缺少字母的词等)。
关于regex - 将缩写与字典匹配的最快方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21013204/