文字列の 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)
.