そのため、文字列の配列で特定の文字/文字を含む単語を見つけるアルゴリズムを考え出そうとしています。
母音が e の単語が必要な場合は、以下のセットから単語 apple と hello を取得します。
{リンゴ、鳥、こんにちは}
特定の文字を含む単語を見つけるには、配列内のすべての文字を調べ、各単語のすべての文字を調べる必要がありますか?
リストを並べ替えてから検索するという賢い方法はありますか?
また、このアルゴリズムの実行時間は? O(n) または O(n*m) と見なされますか? ここで、n は辞書内の単語数、m は配列内の各単語の長さです。
特定の文字を含む単語を見つけるには、その文字を少なくとも 1 回読む必要があります。したがって、O(n*m) のランタイムを指定して、各単語から各文字に 1 回到達する必要があります。ここで、n は単語数、m は単語の平均長です。そうです、各単語から各文字を検索する必要があります。
さまざまな文字に対して多くのクエリを実行する場合は、すべての単語に対して 1 回のパスを実行し、それらの単語をそれらが離れている文字にマップできます。つまり、apple => a、p、l、e セットです。次に、その文字を含むすべての単語を保持する 26 個のセットがあります ('a' : [りんご]、'b' : [鳥]、'c' : []、... 'l' : [りんご、こんにちは]、 ...)。クエリの数が単語セットのサイズに比例して増加すると、O(1) の償却ルックアップ時間になりますが、初期化の複雑さはまだ O(n*m) あります。