いくつかの条件を満たす最小文字列の検索

Question

最近、インタビュー中に次の問題が発生しました。

文字列Sが与えられたら、S2がSの部分列であり、SがS2 +逆行（S2）の部分列であるように、別の文字列S2を見つける必要があります。ここで「+」は連結を意味します。与えられたSに対して可能な限り短いS2の長さを出力する必要があります。

これは動的プログラミングの問題だと言われましたが、解決できませんでした。誰かがこの問題で私を助けることができますか？

編集 -

Oでこれを行う方法（N ）以下であります。

Answer 1

Sからの各文字は、S2に含まれていても、そうでなくてもよい。我々は2例をしようと再帰構築することが可能で：Sの

• を最初の文字をカバーするために使用されている、Sの
• 最初の文字は、カバーに使用 ない

との最小値を計算しますこれらの2つのカバー。これを実装するには、すでに選択されているS2 +反転（S2）でSのどれがカバーされているかを追跡すれば十分です。

どのような結果が（カバーが見つかり、カバーできない）最適化があり、何かをカバーしない場合はカバーの最初の文字を取る必要はありません。

シンプルなPython実装：

cache = {} 

def S2(S, to_cover): 
    if not to_cover: # Covered 
     return '' 
    if not S:   # Not covered 
     return None 
    if len(to_cover) > 2*len(S): # Can't cover 
     return None 
    key = (S, to_cover) 
    if key not in cache: 
     without_char = S2(S[1:], to_cover)  # Calculate with first character skipped 
     cache[key] = without_char 
     _f = to_cover[0] == S[0] 
     _l = to_cover[-1] == S[0] 
     if _f or _l: 
      # Calculate with first character used 
      with_char = S2(S[1:], to_cover[int(_f):len(to_cover)-int(_l)]) 
      if with_char is not None: 
       with_char = S[0] + with_char # Append char to result 
       if without_char is None or len(with_char) <= len(without_char): 
        cache[key] = with_char 
    return cache[key] 

s = '21211233123123213213131212122111312113221122132121221212321212112121321212121132' 
c = S2(s, s) 
print len(s), s 
print len(c), c 

Answer 2

のS2は "りんご" であるとしましょう。だから、

S2 + reverseS2> = S> = S2
"appleelppa"> = S> = "りんご"

：その後、我々はこの仮定を行うことができます与えられたSは、 "リンゴ"を含むもので、 "リンゴテッペ"以上のものになります。それは "appleel"または "appleelpp"とすることができます。

String S ="locomotiffitomoc"; 
// as you see S2 string is "locomotif" but 
// we don't know S2 yet, so it's blank 
String S2 = ""; 
for (int a=0; a<S.length(); a++) { 
    try { 
     int b = 0; 
     while (S.charAt(a - b) == S.charAt(a + b + 1)) 
      b++; 
     // if this for loop breaks that means that there is a character that doesn't match the rule 
     // if for loop doesn't break but throws an exception we found it. 
    } catch (Exception e) { 
     // if StringOutOfBoundsException is thrown this means end of the string. 
     // you can check this manually of course. 
     S2 = S.substring(0,a+1); 
     break; 
    } 
} 
System.out.println(S2); // will print out "locomotif" 

おめでとうございますが、S2が見つかりました。

Answer 3

この問題には2つの重要な側面があります。

1. S2が逆（S2）の部分文字列としてSを必要とするため、S2は少なくとも の長さでなければなりません。 S2の連結後
2. および逆方向（S2）は、 アルファベットだから溶液はSで終了するSの中心から確認するよう

を繰り返しパターンが存在します任意の連続した要素に対して。見つかった場合は、図のように両側の要素をチェックしてください。

あなたは、文字列の最後まで到達することができれば今、その要素の最小数（結果は）最初からあなたが連続する要素を見つけ点までの距離です。この例では、そのCのすなわち3

私たちは、これが常に発生しないことを知っています。つまり、中央で連続した要素を見つけることができない場合があります。連続した要素が中心の後にあるとしましょう。同じテストを行うことができます。

主な文字列

サブストリング

連結した文字列

は今トンに到着彼は大きな疑いを持った。なぜ、私たちは中心から出発して左側だけを考えますか？答えは簡単です。連結された文字列はS + reverse（S）によって作成されます。したがって、部分文字列の最後の要素は、連結された文字列内で連続していると確信しています。メインの文字列の最初の半分の繰り返しは、少なくとも最終的に連結された文字列にn個のアルファベットを入れなければならない方法はありません。

今や複雑さの問題： 連続するアルファベットを検索すると、最大値O（n） ここで、要素の反復的なチェックを行うと、O（n）の最悪の複雑さが得られます。すなわち最大n/2比較。我々は複雑すなわちO（N * N）との乗法関係を持っているので、 私たちは、第2のチェックをやって何度も失敗することがあります。

私はこれが正しい解決策であると考えていると、まだ抜け穴を見つけることができませんでした。