时间戳

首页 > 解决方案 > 给定字符串和（列表）单词，返回包含字符串的单词（最优算法）

python - 给定字符串和（列表）单词，返回包含字符串的单词（最优算法）

问题描述

假设我们有一个唯一单词列表和一个子字符串。

我正在寻找一种最佳算法，它返回包含子字符串的单词。

一般应用是：给定一个数据库，使用搜索栏过滤结果。

Python中的一个简单实现：

def search_bar(words, substring):
    ret = []
    for word in words:
        if substring in word:
            ret.append(word)
    return ret

words = ["abc", "bcd", "thon", "Python"]
substring = "on"

search_bar(words, substring)

这将返回：

["thon", "Python"]

在 timeO(lenght_of_list * complexity_of_in)中，complexity_of_in在某种程度上取决于子字符串的长度和单个单词的长度。

我要问的是是否有更快的实施。鉴于我们可以将列表预处理为我们想要的任何结构。

只是重定向到问题/答案将是惊人的。

注意：如果这种结构不需要太长时间来添加一个新单词会更好。但主要它不需要能够添加任何东西，因为 Python 示例没有。

另外，我不确定这个问题的标签......

标签： pythonregex

解决方案

也许使用

word.find(substring)

反而

substring in word

并作为变体：

def search_bar(words, substring):
    return list(filter(lambda word: word.find(substring)!=-1, words))

推荐阅读