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

Question

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

如果我想要带有元音 e 的单词，我会从下面的集合中得到单词 apple 和 hello。

{苹果，鸟，你好}

要查找具有特定字符的单词，我是否需要查看数组中的所有字母并查看每个单词的每个字符？

有没有一种聪明的方法可以通过对列表进行排序然后以某种方式搜索？

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

Answer 1

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

现在，如果您要对不同的字母进行大量查询，您可以对所有单词进行一次遍历并将这些单词映射到它们所在的字符。即苹果 => a, p, l, e 集合。那么你将有 26 个集合，其中包含具有该字符的所有单词（'a'：[apple]，'b'：[bird]，'c'：[]，...'l'：[apple，hello]， ...）。随着查询数量相对于单词集大小的增加，您最终会得到 O(1) 的分摊查找时间——尽管您仍然有 O(n*m) 初始化复杂度。