2

文字列の数は 30000 のように膨大になる可能性があります。N 個の文字列が与えられた場合、英語のアルファベットを変更した後、どの文字列が辞書編集的に最小になるかを出力します。例えばacdbe......

たとえば、文字列が次の場合:

omm
moo
mom
ommnom

「お母さん」は、元の英語のアルファベットで辞書編集的に最も少ないです。アルファベットの「m」と「o」を入れ替えることで、単語「omm」を最小にすることができます (「abcdefghijklonmpqrstuvwxyz」)。あなたが辞書編集的に作ることができない他のものは、あなたが何をしても、最初に。

これを行うための速い方法はありますか?考えられるすべてのアルファベットを試す以外に、これにアプローチする方法はありません

4

1 に答える 1

0

文字列の 1 つ (たとえば s) を小さくすることができます。これを、グラフ内のサイクルの検出の問題に変えることができます。方法は次のとおりです。

26 個の頂点からなるグラフを考えてみましょう: V = { 'a', 'b', ..., 'z' } s が最小であると仮定し、s の文字を順番に考えます。

最初の文字を検討している場合、s[0] は他のすべての文字列 x の x[0] よりも小さくなければならないことがわかっています。次に、同じ文字ではないすべての x について、s[0] から x[0] へのグラフのエッジを追加します。エッジは「より小さい」という意味です。次に 2 番目の文字を考えますが、最初の文字が s と同じ文字列だけを見てください。同じことを行います -このレデュース セットのすべての y に対してs 1から y 1へのエッジを追加します。次に、3 番目の文字に移動し、1 番目と 2 番目の文字が同じ文字列のみを検討します。などなど (最初に s 以外のすべての文字列を含む Set データ構造を使用でき、それから削除します) .

グラフを作成したら、サイクルがあるかどうかを知りたいと思います。実際、循環がある場合、これはこの s を最小にすることができないことを意味します。なぜなら、循環に従うと、循環の最初の文字をそれ自体よりも小さくする必要があるためです。これは不可能です。一方、循環がない場合、グラフは DAG (有向非巡回グラフ) であり、どの DAG もトポロジー的に並べ替えることができます。つまり、その頂点 (つまり、アルファベットの文字) をエッジが小さいものから大きいものへと変化するようにします。この順序では、グラフがどのように作成されたかにより、s が最小になります。

有向グラフのサイクルの検出について調べることができます。これは非常に一般的な問題であり、その複雑さはO(|V|+|E|). この場合 |V| = 26 および |E| <= n (グラフにエッジを追加するたびに、チェックする文字列のセットを 1 つ減らすため)。

したがって、複雑さはO(n)です。

各文字列をチェックしたい場合、全体の複雑さはO(n^2).

于 2012-12-17T00:25:44.367 に答える