これは、文字列を最小限の操作で回文に変換するための問題の状態です。レーベンシュタイン距離に似ていることは知っていますが、 まだ解決できません
たとえば、入力mohammadsajjadhossainの場合、出力は8です。
5435 次
2 に答える
9
弦とその逆でレーベンシュタイン距離を実行します。解は、左下から右上に向かう DP 配列の対角線の最小演算と、対角線のすぐ上とすぐ下の各エントリになります。
これが機能するのは、対角線に沿ったエントリが文字列の最初の i 文字と最後の Ni 文字を等しくするために必要な最小限の編集を表し、そのすぐ上とすぐ下のエントリが奇数長になる文字列の最小値を表しているためです。 -over) 文字は何にも一致しません。
于 2011-01-19T16:42:18.363 に答える
2
回文のピボット ポイントごとに 1 つずつ、限られた数のレーベンシュタイン距離を計算するだけで済みます。ピボット ポイントは文字にすることも、2 文字の間にすることもできるため、長さ n の文字列には 2n-1 個のピボット ポイントがあります。ピボット ポイントごとに、ピボット ポイントの前の文字のレーベンシュタイン距離と、その後の文字の逆のレーベンシュタイン距離を計算します。
(m)ohammadsajjadhossain: Levensthein("", "niassohdajjasdammaho")
m ohammadsajjadhossain: Levensthein("m", "niassohdajjasdammaho")
m(o)hammadsajjadhossain: Levensthein("m", "niassohdajjasdammah")
mo hammadsajjadhossain: Levensthein("mo", "niassohdajjasdammah")
mo(h)ammadsajjadhossain: Levensthein("mo", "niassohdajjasdamma")
moh ammadsajjadhossain: Levensthein("moh", "niassohdajjasdamma")
等
次に、これらの距離の最小値を取ります。速度が重要な場合は、これらの呼び出しの多くを最適化できます。
于 2011-01-19T17:23:49.043 に答える