时间戳

首页 > 解决方案 > 查找字符串中每个不同字符的所有位置的最快方法

python - 查找字符串中每个不同字符的所有位置的最快方法

问题描述

假设我们有一个字符串，比如“122113”，我们应该找到字符串中每个字符的所有出现。

一个天真的方法是这样的：

string = str( raw_input() )  # for example: "122113"
distinct_char = list( set(string) )
occurrences=[]
for element in distinct_char:
    temp=[]
    for j in range(len(string)):
        if(string[j]==element):
            temp.append(j)
    occurrences.append(temp)
print(occurrences)  # output for "122113" would be [[0, 3, 4], [1, 2], [5]]
                    #because 1 occurrs at : 0, 3, 4
                    #        2 occurrs at : 1, 2
                    #        3 occurrs at : 5

但是，如果 String 的长度很大，这会很慢。 那么，有没有更快的解决方案呢？

（考虑字符串仅由低位英文字母组成，字符串的长度可能为 $10^12$

标签： pythonstring

解决方案

您应该使用 defaultdict（以空列表作为默认值）并在遍历字符串时更新索引列表：

from collections import defaultdict
string = str(raw_input())
occurences = defaultdict(list)
for i, c in enumerate(string):
  occurences[c].append(i)
print occurences

然后使用列表推导来获取您的出现列表：

occurences = [l for l in occurences.values()]

推荐阅读