如何在列表中找到以给定字符串开头的元素的索引

例如,如果我有字符串列表和给定的字符串

list=['aab','bab','ccab','dab']
s='da'

and if I want to find index of element that starts with s I know I can do this like this

i=0
for l in list :
    if l[0:len(s)]==s:
        print(i)
        break
    i+=1 

但是时间复杂度是O(n)。问题是,可以在O(1)中完成,因为我知道的唯一方法是使用哈希函数,但是我不确定在这种情况下是否可以使用哈希函数。

评论
大三元
大三元

You can use a list comprehension and enumerate:

indexes = [i for i, el in enumerate(l) if el.startswith(s)]
点赞
评论
旧言虐心
旧言虐心

获得O(1)的唯一方法是牺牲空间。创建一个字典,将所有可能的查询作为键,并将结果作为值。

例如:

lookup = {
    "a": {0},
    "b": {1},
    "c": {2},
    "d": {3},
    "aa": {0},
    "ba": {1},
    "ca": {2},
    "da": {3},
    # etc
}
点赞
评论