"string reduction"チャレンジの解決

Question

"String reduction"の問題をinterviewstreet.comから解決するには、さまざまな議論やコードの試みが見られましたが、いずれも動的プログラミングではありません。 Dynamic Programmingセクションの下にリストされている

次のように、問題が記述されている：

、b、cの年代からなる文字列を考えると、我々は以下の操作を行うことができます任意の2つの隣接の異なる文字を取り、それを置き換えます3番目の文字と一緒に。たとえば、 'a'と 'c'が隣接している場合、 'b'で置き換えることができます。

をこの操作を適用することによって生じる最小の文字列は何ですか？

問題が効果的にすべての可能な置換のツリーを作成し、徹底的力まかせ探索を使用して解決することができます。

// this is more or less pseudo code from my head 
int GetMinLength(string s) 
{ 
    // solve edge cases 
    if (s.Length == 1) return 1; 
    if (s.Length == 2) return ReduceIfPossible(s); 

    // recursive brute force 
    int min = s.Length; 
    for (int i = 0; i<s.Length-1; i++) 
    { 
     if (s[i] != s[i+1]) 
     { 
      var next = GetMinLength(
        s.Substring(0, i) + 
        Reduce(s[i], s[i + 1]) + 
        s.Substring(i + 2) 
       ); 

      if (next < min) min = next; 
     } 
    } 
} 

これは明らかに（N <= 100）N大きなために失敗したので、私は破るしようとしていますそれを小さなサブ問題に分解し、それらをメモし、結果をマージします。

問題は、動的プログラミング（つまり、サブ問題の結果を「マージ」する）を適用するために必要な"optimal substructure"の状態を判断できないという問題です。文字列の一部を最小限にしても、最終的な文字列が本当に最小の解決方法になるという保証はありません。

この場合、サブソリューション「状態」は最終的な解決策に統合される可能性がありますか？

Answer 1

これを難しくするのは、2つの動的プログラミング問題を連続して扱う必要があることです。

1. 、開始位置によって、あなたと羽目文字で、その文字にすることができるブロックされている可能性端部位置のすべてのテーブルを作成します。
2. 文字列の最後のi文字に縮小できる最小の長さです。 （手順1で作成した表は、この問題を再帰的に減らして既に問題を解決しています）

2番目の答えが表示されます。すでに最初の問題を解決していればはるかに簡単です。

Answer 2

まず、解理論を説明する構造を作成します。これには、考慮される文字数とこれまでにエンコードされた文字列、そして最悪の場合と理論のための最良の場合が含まれます。

冒頭には1つの理論しかありません。処理される文字はありません。最長の場合は長さ1の文字列です（たとえば、ルールが常に適用され、文字列を1文字に減らすことができます。最悪の場合はルールが適用されない場合はNです）。

encoded string = ""; 
encoded index = 0; 
worst case = N; 
best case = 1; 

インデックスを1つインクリメントし、エンコードされた文字列に文字を追加します。ルールが適用されない場合は、その理論をそのままにしておきます。ルールが適用される場合は、ルールを適用するか適用しないかを決定します。したがって、文字を追加すると、最後の文字に適用できる各ルールの理論が複製され、ルールが適用されないバージョンが1つ保持されます。そして、それぞれの理論について最善のケースと最悪のケースを更新します。

最初に理論の数は非常に急増します。しかし、最終的には、いくつかの理論の最悪の場合が他の理論の最良の場合よりも良い状況に来る。

インデックスを前倒しすると、最悪の場合が最も良い理論よりも最良の場合の理論が削除されます。指数がNに近づくにつれて、理論の大半は脱落するだろう。

Answer 3

スポイラーアラートコード：

public static int findMinReduction(String line){ 
    //Pseudocode: 
    //Count the number of occurences of each letter in the input string. 
    //If two of these counts are 0, then return string.length 
    //Else if (all counts are even) or (all counts are odd), then return 2 
    //Else, then return 1 

    int len = line.length(); 
    String a_reduce = line.replaceAll("c", "").replaceAll("b", ""); 
    String b_reduce = line.replaceAll("a", "").replaceAll("c", ""); 
    String c_reduce = line.replaceAll("a", "").replaceAll("b", ""); 

    int a_occurances = a_reduce.length(); 
    int b_occurances = b_reduce.length(); 
    int c_occurances = c_reduce.length(); 

    if ((a_occurances == b_occurances && a_occurances == 0) || 
     (a_occurances == c_occurances && a_occurances == 0) || 
     (b_occurances == c_occurances && b_occurances == 0)){ 
     return len; 
    } 
    else{ 
     if (a_occurances % 2 == 0 && 
      b_occurances % 2 == 0 && 
      c_occurances % 2 == 0){ 
      return 2; 
     } 
     if (a_occurances % 2 != 0 
      && b_occurances % 2 != 0 && 
      c_occurances % 2 != 0){ 
      return 2; 
     } 
    } 
    return 1; 
} 

複雑：これは（n）の時間計算動作は、入力サイズが増加するにつれてOである

、行うべき仕事の量であります入力の大きさに比例します。稲妻が素早く、メガバイトサイズの文字列を処理し、それを数秒で処理することができます。

アルゴリズムは、このアルゴリズムが働く理由の完全な分析をここで見つける：その通り

stumped on a Java interview, need some hints