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

Question

所以我试图找出一个算法来找到字符串中的特定字符/字母的单词。

如果我想要元音e的单词，我会从下面的单词中获得单词apple和hello。

{苹果，鸟，你好}

若要寻找特定字符的话，我需要通过所有的字母来看待数组中，并通过每个单词的每个字符看？

有没有一种聪明的方式，也许通过整理列表然后搜索？

另外，这个算法的运行时间是多少？ 它会被认为是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）的初始化复杂度。