找到使2个字符串相等所需的最小移动量

Question

这是一个在线编码挑战(已完成)的问题.
我只需要一些关于如何处理的逻辑.

问题陈述:
我们有两个字符串A和B,它们具有相同的超级字符集.我们需要更改这些字符串以获得两个相等的字符串.在每次移动中,我们都可以执行以下操作之一:

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

可以对任一字符串执行移动.为获得两个相等的字符串,我们需要
的最小移动次数是多少？

输入格式和约束:输入
的第一行和第二行包含两个字符串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.这两个字符串现在相等.

编辑:这是我的第一次尝试,但我输错了.有人可以指导我的方法有什么问题.

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;
}

Answer 1

看一下这个例子：

aaaaaaaaab
abaaaaaaaa

您的解决方案：8

aaaaaaaaab -> aaaaaaaaba -> aaaaaaabaa -> aaaaaabaaa -> aaaaabaaaa -> 
aaaabaaaaa -> aaabaaaaaa -> aabaaaaaaa -> abaaaaaaaa

正确的解决方案：2

aaaaaaaaab -> baaaaaaaaa -> abaaaaaaaa

您应该检查是否在另一个方向上进行交换会带来更好的结果。

但是有时您还会破坏字符串的前一部分。例如：

caaaaaaaab
cbaaaaaaaa

caaaaaaaab -> baaaaaaaac -> abaaaaaaac

您需要在此处进行另一次交换，以将“ c”放回第一位。

正确的算法可能甚至更复杂，但是现在您可以看到解决方案中的问题。

Answer 2

您可以使用动态规划。检查所有交换的可能性，同时存储所有中间结果以及到达那里所需的最少步骤。实际上，您将计算通过多次应用给定规则可以获得的每个可能目标字符串的最小步骤数。计算完所有内容后，您可以打印到达目标字符串所需的最小步骤数。以下是 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"]);