在字符串数组中查找特定字符/字母的算法？

Question

因此，我试图提出一种算法，在字符串数组中查找带有特定字符/字母的单词。

有没有一个聪明的方法，也许通过排序列表，然后以某种方式搜索？

另外，这个算法的运行时间是多少？它会被认为是O(n)还是O(n*m)？其中n是字典中的单词数，m是数组中每个单词的长度。

Answer 1

为了找到带有特定字符的单词，您需要至少阅读该字符一次。因此，您必须访问每个单词中的每个字符一次，给出一个运行时O(n*m)，其中n是单词数，m是平均单词长度。所以是的，您需要从每个单词中查找每个字符。

现在，如果你要对不同的字母进行大量的查询，你可以对所有单词进行一次遍历，然后将这些单词映射到它们所在的字符。即apple=>a,p,l,e集。然后您将有26个集合，其中包含所有带有该字符的单词('A':[apple]、'B':[bird]、'C':[]、...'L':[apple,hello]、...)。随着查询的数量相对于单词集的大小而增加，您最终将得到O(1)的摊销查找时间--尽管您仍然有O(N*M)的初始化复杂度。