10

这是来自在线编码挑战之一的问题（已完成）。
我只需要一些关于如何处理的逻辑。

问题陈述：
我们有两个字符串 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;
}
4

5 回答 5

5

看看这个例子：

aaaaaaaaab
abaaaaaaaa

您的解决方案：8

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

正确的解决方案：2

aaaaaaaaab -> baaaaaaaaa -> abaaaaaaaa

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

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

caaaaaaaab
cbaaaaaaaa

caaaaaaaab -> baaaaaaaac -> abaaaaaaac

您需要在此处再次交换以将“c”放回首位。

正确的算法可能更复杂，但您现在可以看到您的解决方案有什么问题。

于 2013-08-29T13:34:24.957 回答
1

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

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

由于h(x)是可接受的（因为单个转换不能将超过 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 回答
0

试试这个代码。希望这会帮助你。

公共类 TwoStringIdentical {

static int lcs(String str1, String str2, int m, int n) {
    int L[][] = new int[m + 1][n + 1];
    int i, j;

    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;

            else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                L[i][j] = L[i - 1][j - 1] + 1;

            else
                L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
        }
    }

    return L[m][n];
}

static void printMinTransformation(String str1, String str2) {
    int m = str1.length();
    int n = str2.length();
    int len = lcs(str1, str2, m, n);
    System.out.println((m - len)+(n - len));
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String str1 = scan.nextLine();
    String str2 = scan.nextLine();
    printMinTransformation("asdfg", "sdfg");
}

}

于 2018-01-31T19:04:30.463 回答
0

这是此问题的 ruby​​ 逻辑，将此代码复制到 rb 文件并执行。

str1 = "education" #Sample first string
str2 = "cnatdeiou" #Sample second string

moves_count = 0
no_swap = 0
count = str1.length - 1

def ends_swap(str1,str2)    
    str2 = swap_strings(str2,str2.length-1,0)
    return str2
end

def swap_strings(str2,cp,np)
    current_string = str2[cp]
    new_string = str2[np]
    str2[cp] = new_string
    str2[np] = current_string
    return str2
end

def consecutive_swap(str,current_position, target_position)
    counter=0
    diff = current_position > target_position ? -1 : 1
    while current_position!=target_position
        new_position = current_position + diff
        str = swap_strings(str,current_position,new_position)
        # p "-------"
        # p "CP: #{current_position}   NP: #{new_position} TP: #{target_position}  String: #{str}"
        current_position+=diff
        counter+=1
    end
    return counter,str
end

while(str1 != str2 && count!=0)
    counter = 1
    if str1[-1]==str2[0]
        # p "cross match"
        str2 = ends_swap(str1,str2)
    else
        # p "No match for #{str2}-- Count: #{count}, TC: #{str1[count]}, CP: #{str2.index(str1[count])}"
        str = str2[0..count]
        cp = str.rindex(str1[count])
        tp = count
        counter, str2 = consecutive_swap(str2,cp,tp)
        count-=1        
    end
    moves_count+=counter    
    # p "Step: #{moves_count}"
    # p str2
end

p "Total moves: #{moves_count}"

请随时提出对此代码的任何改进。

于 2017-11-24T17:23:45.427 回答