10

これは、オンライン コーディング チャレンジ (完了済み) の 1 つからの質問です。
どのようにアプローチするかについて、これにはいくつかのロジックが必要です。

問題文:
同じスーパー セットの文字を持つ 2 つの文字列 A と B があります。これらの文字列を変更して、2 つの等しい文字列を取得する必要があります。各移動では、次の操作のいずれかを実行できます。

1. swap two consecutive characters of a string  
2. swap the first and the last characters of a string

移動はどちらの弦でも実行できます。2 つの等しい文字列を取得するために必要な移動 の最小
数は 何ですか?

入力形式と制約: 入力
の 1 行目と 2 行目には、2 つの文字列 A と B が含まれています。スーパーセットの文字が等しいことが保証されています。 

1 <= length(A) = length(B) <= 2000
All the input characters are between 'a' and 'z'


出力形式:
移動 の最小数を出力の唯一の行に出力します

Sample input:
aab
baa

Sample output:
1

説明:
文字列 aab の最初と最後の文字を交換して、baa に変換します。2 つの文字列が等しくなりました。

編集:これが私の最初の試みですが、間違った出力が得られます。誰かが私のアプローチで間違っていることを教えてくれますか?

int minStringMoves(char* a, char* b) {
    int length, pos, i, j, moves=0;
    char *ptr;
    length = strlen(a);

    for(i=0;i<length;i++) {
        // Find the first occurrence of b[i] in a
        ptr = strchr(a,b[i]);
        pos = ptr - a;

        // If its the last element, swap with the first
        if(i==0 && pos == length-1) {
            swap(&a[0], &a[length-1]);
            moves++;
        }
        // Else swap from current index till pos
        else {
            for(j=pos;j>i;j--) {
                swap(&a[j],&a[j-1]);
                moves++;
            }
        }

        // If equal, break
        if(strcmp(a,b) == 0)
            break;       
   }

   return moves;
}
4

5 に答える 5

1

この問題には、A* アルゴリズムが有効な場合があります。

最初のノードは元の文字列になります。
ゴール ノードはターゲット文字列になります。
ノードの各子は、その文字列のすべての可能な変換になります。
現在のコストg(x)は、これまでの変換の数です。
ヒューリスティックh(x)は、間違った位置にある文字数の半分です。

許容されるためh(x)(1 回の変換で 2 文字を超える文字を正しい位置に配置できないため)、ターゲット文字列へのパスは可能な限り少ない数の変換を提供します。

ただし、基本的な実装は遅すぎる可能性があります。文字列の可能なすべての変換を計算すると、かなりコストがかかります。

ノードの兄弟 (親の子) とその子の間には多くの類似点があることに注意してください。したがって、元の文字列のすべての変換を計算するだけで、そこから、変更された文字を含むデータをコピーして再計算することができます。

于 2013-09-06T08:39:27.350 に答える
0

動的計画法を使用できます。すべての中間結果とそこにたどり着くまでの最小ステップ数を保存しながら、すべてのスワップの可能性を調べます。実際には、指定されたルールを何度も適用することによって取得できるすべてのターゲット文字列の最小ステップ数を計算します。すべてを計算したら、ターゲット文字列に到達するために必要な最小ステップ数を出力できます。JavaScript のサンプル コードと、"aab" および "baa" の例での使用法を次に示します。

function swap(str, i, j) {
   var s = str.split("");
   s[i] = str[j];
   s[j] = str[i];
   return s.join("");
}

function calcMinimumSteps(current, stepsCount)
{
   if (typeof(memory[current]) !== "undefined") {
      if (memory[current] > stepsCount) {
          memory[current] = stepsCount;
      } else if (memory[current] < stepsCount) {
          stepsCount = memory[current];
      }
   } else {
      memory[current] = stepsCount;
      calcMinimumSteps(swap(current, 0, current.length-1), stepsCount+1);
      for (var i = 0; i < current.length - 1; ++i) {
          calcMinimumSteps(swap(current, i, i + 1), stepsCount+1);
      }
   }
}

var memory = {};
calcMinimumSteps("aab", 0);
alert("Minimum steps count: " + memory["baa"]);
于 2013-08-29T13:06:36.787 に答える