回文を形成する挿入の最小数を見つける JavaScript プログラム

文字列が与えられた場合、最終的な文字列が回文になるように、その文字列内の任意の場所に挿入する必要がある異なる文字の最小数を見つける必要があります。回文は、その逆の文字列とまったく同じ文字列です。この問題は動的にプログラムされているので、最初に再帰法を使用し、次にそれを暗記し、最後に暗唱法の表を見ることになります。

再帰的メソッド

例

リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

時間と空間の複雑さ 挿入ごとに選択を行うため、上記のコードの時間計算量は O(2^N) です。N は指定された文字列のサイズです。

上記のコードの空間複雑さは、再帰呼び出しの場合は O(N) です。

記憶方法

例

リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

計算結果を保存するため、上記のコードの時間計算量は O(N^2) です。

ここでは余分なスペースを使用しているため、上記のコードのスペース複雑さは O(N^2) です。

動的プログラミング手法

例

リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

ここではネストされた for ループを使用しているため、上記のコードの時間計算量は O(N^2) です。

ここでは余分なスペースを使用しているため、上記のコードのスペース複雑さは O(N^2) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、JavaScript プログラミング言語を使用して、再帰からメモ化、表作成までの 3 つのメソッドを実装し、特定の文字列を回文にするために必要な最小挿入数を見つけました。回文は、その逆の文字列とまったく同じ文字列です。つまり、同じ文字を表から読んでも裏からでも読み取ることができます。

以上が回文を形成する挿入の最小数を見つける JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。