15

これは非常に興味深いインタビューの質問です：

単語が与えられたら、それに最も少ない数の文字を追加して、回文に変換します。

たとえば、「hello」が指定された文字列である場合、結果は「hellolleh」になります。「coco」を指定すると、「cococ」になります。

私が考えることができる1つのアプローチは、元の文字列の最後に文字列の逆を追加してから、最後から余分な文字を削除することです。しかし、これを効率的に行う方法がわかりません。誰かアイデアはありますか？

4

4 に答える 4

10

わかった！これが私の2回目の試みです。

アイデアは、回文を完成させるために余分な文字を追加するときに、文字列の最後にある文字の数を再利用できるかどうかを調べたいということです。これを行うために、KMP文字列照合アルゴリズムの変更を使用します。KMPを使用して、元の文字列の逆を検索します。文字列の最後に到達すると、文字列の逆と文字列の最後にある元の文字列との間で可能な限り一致するようになります。例えば：

HELLO
    O

1010
 010

3202
 202

1001
1001

この時点で、元の文字列が回文でない限り、KMPは通常「一致なし」と言います。ただし、現在、文字列の裏側がどれだけ一致しているかがわかっているので、代わりに、まだ欠落している文字の数を把握して、文字列の最後に追加することができます。最初のケースでは、が欠落していますLLEH。2番目のケースでは、が欠落しています1。3番目では、が欠落しています3。最後のケースでは、最初の文字列が回文であるため、何も欠落していません。

このアルゴリズムの実行時間は、標準のKMP検索の実行時間に、文字列を逆にするために必要な時間を加えたものです：O（n）+ O（n）= O（n）。

だから今、正しさを議論する。これにはいくらかの努力が必要になります。最適な答えを検討してください。

   | original string | | extra characters |

これを最後から逆方向に読んでいると仮定しましょう。つまり、少なくとも元の文字列の逆を読んでいるということです。この反転した弦の一部は、元の弦自体の本体に向かって後方に伸びています。実際、追加される文字数を最小限に抑えるには、これが文字列自体に戻る可能性のある最大の文字数である必要があります。ここでこれを見ることができます：

   | original string | | extra characters |
           | overlap |

では、KMPステップで何が起こりますか？さて、それ自体の内部で文字列の逆を探すとき、KMPは文字列全体で機能するため、常に可能な限り長い一致を維持します。これは、KMPが文字列の終わりに到達したときに、KMPが失敗した場合にのみ候補一致の開始点を前方に移動するため、KMPが維持する一致部分が可能な限り最長の一致になることを意味します。その結果、この可能な限り長いオーバーラップがあるため、最後に必要な文字数を可能な限り短くします。

これが機能するかどうかは100％確信できませんが、私が投げることができるすべての場合にこれが機能するようです。正当性の証明は妥当なように見えますが、正式なKMPベースの証明はおそらく少し注意が必要なため、少し手間がかかります。

お役に立てれば！

于 2012-03-11T09:02:04.887 に答える
5

答えるために、私はこの素朴なアプローチを取ります：

  1. 0文字が必要なときは？文字列の場合は回文です
  2. 1文字必要なときは？最初の文字列を除いて回文である場合
  3. 2文字必要なときは？2つの開始文字を除いて、文字列が回文である場合
  4. などなど...

したがって、アルゴリズムは次のようになります。

  for index from 1 to length
   if string.right(index) is palindrome
    return string + reverse(string.left(index))
   end
  next

編集

私はPythonの人ではありませんが、上記の擬似コードの単純な実装は次のようになります。

>>> def rev(s): return s[::-1]
... 
>>> def pal(s): return s==rev(s)
... 
>>> def mpal(s):
...  for i in range(0,len(s)):
...   if pal(s[i:]): return s+rev(s[:i])
... 
>>> mpal("cdefedcba")
'cdefedcbabcdefedc'
>>> pal(mpal("cdefedcba"))
True
于 2012-03-11T09:21:03.763 に答える
4

単純な線形時間ソリューション。

文字列をSと呼びましょう。

f（X、P）をXとPの最長の共通プレフィックスの長さとします。f（S [0]、rev（S））、f（S [1]、rev（S））、..を計算します。ここで、S[k]は位置kから始まるSの接尾辞です。明らかに、k + f（S [k]、rev（S））= len（S）となるような最小のkを選択する必要があります。つまり、最後にk文字を追加するだけです。kが0の場合、刺し傷はすでに回文です。k = len（S）の場合、リバース全体を追加する必要があります。

すべてのS[i]についてf（S [i]、P）をすばやく計算する必要があります。これは難しい部分です。Sの接尾辞木を作成します。ツリーを走査し、すべてのノードを最長の共通接頭辞の長さでPで更新します。葉の値はf（S [i]、P）に対応します。

于 2012-03-11T12:07:45.373 に答える
2

まず、「a」と「aa」が回文であることを念頭に置いて、文字列の回文性をテストする関数を作成します。彼らは回文ですよね？

入力が回文の場合は、それを返します（0文字を追加する必要があります）x[length]からx[1]までループし、文字列x [i] ..x[length]のサブセットが回文であるかどうかを確認します。最長の回文を見つけるために。

最長の回文の前の入力文字列から部分文字列を取得し、それを逆にして最後に追加すると、追加によって最短の回文が作成されます。

ココ=>c+ oco => c + oco + c

mmmeep => mmmee + p => mmmee + p + eemmm

于 2012-03-11T09:17:37.700 に答える