algorithm - ある文字列の文字が別の文字列に含まれる

Question

ある文字列のすべての文字が別の文字列に含まれていることを確認する方法。たとえば、abc が string1、cbade が string2 の場合、string1(abc) 内のすべての文字はすべて string2 に含まれます。実際には簡単に見えますが、それを行うには最速の方法が必要なので、それでも非常に難しく、1週間を費やして1つの解決策を得ることができません.

Answer 1

文字に数値を簡単に割り当てることができる言語 (ほとんどの言語) を使用している場合は、ルックアップ テーブルを使用してこれをさらに高速化できます。

1. ルックアップ テーブル、各文字に 1 つのスロット
2. ルックアップ テーブルの string2 の文字を訪問
3. string1 の文字がアクセスされていることを確認してください
4. ???
5. 利益

ランタイム: A + B
ランスペース: A + B + N、N は可能な文字数です。(C: 256、Java: 65536)

そうでない場合は、文字間の任意の順序を確立できるはずです。その場合:

1. 両方の文字列をアルファベット順に並べ替える
2. 二分探索 (最後に見つかった一致の位置を非常に適切な初期推定として使用できます)
3. ???
4. 利益

ランタイム: A*log(A) + B*log(B) + A*log(B)
ランスペース: A + B

Answer 2

2 つの文字列のすべての文字を 2 つのセットに入れ、一方が他方のサブセットであることを確認します。Python の場合:

>>> set("abc").issubset(set("cbade"))
True

Answer 3

これは O(n) で行うことができます。最初に、2 番目の文字列に存在する文字のハッシュ テーブルを作成します。次に、最初の文字列の文字を繰り返し処理し、その文字がハッシュテーブルにエントリがあることをアサートします。

Answer 4

可能な文字数が少ないため (256 と仮定)、サイズ 256 の固定配列を使用できます。最初に各ビットをゼロに設定し、次に最初の文字列の任意の文字にアクセスすると、関連するビットを配列に設定します。 2番目の配列をトラバースし、設定するビットがない場合は、それらすべてが前の文字列にあったことを意味し、2番目の文字列のすべての文字が最初の文字列で使用可能であると言えます。関連付けビットがまだ設定されていない場合、最初の文字列に 2 番目の文字列が含まれていないと言えます。このアルゴリズムは、時間では O(n)、メモリでは O(1) (つまり、O(1) 外部メモリ) です。