找到使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

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

Answer 2

A*算法可能适用于此问题。

初始节点将是原始字符串
目标节点将是目标字符串
节点的每个子节点都将是该字符串的所有可能转换
当前成本g（x）只是迄今为止的转换次数
启发式h（x）是错误位置字符数的一半。

由于h（x）是允许的（因为单个转换不能在其正确位置放置超过2个字符），因此目标字符串的路径将提供尽可能少的转换次数。

然而，初级实现可能会太慢。计算字符串的所有可能转换将是相当昂贵的。

请注意，节点的兄弟姐妹（父节点的子节点）与其子节点之间有很多相似之处。因此，您可以计算原始字符串的所有转换，并从那里简单地复制和重新计算涉及更改字符的数据。

Answer 3

看看这个例子：

aaaaaaaaab
abaaaaaaaa

您的解决方案：8

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

正确的解决方案：2

aaaaaaaaab -> baaaaaaaaa -> abaaaaaaaa

您应该检查在另一个方向上交换是否会提供更好的结果。

但有时你也会破坏字符串的前一部分。如：

caaaaaaaab
cbaaaaaaaa

caaaaaaaab -> baaaaaaaac -> abaaaaaaac

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

正确的算法可能更复杂，但现在您可以看到解决方案中的错误。