文字列を回文に変換するために必要な挿入の最小数を見つける必要があります。注: 挿入は、任意の場所、末尾、または内部で発生する可能性があります。最後だけだったら、ここで質問があります。
O(N**2)したがって、これは次の簡単なトリックで時間内に実行できることがわかりました。
- 文字列を s1 とします。それを逆にします。s2 とする．長さは とし
lます。 - 次に、s1 と s2 の最長共通部分列を見つけます。その長さを とする
x。 - 答えは
l-xです。
たとえば、 としますs1 = abcda。したがってs2 = adcba。長さは 5 です。最長の共通サブシーケンスはaba長さ 3 です。したがって、挿入の最小数は であり5-3 = 2、これが実際の答えであり、結果の文字列は -です。adcbcda
ただし、その背後にあるロジックは理解できません。なぜそれが機能するのか、誰かが私に説明できますか?
そして、これに対するO(N)解決策はありますか？