查找字符串數組中特定字符/字母的算法？

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）的初始化複雜度。