Java最小字符串运动？(Java minimum string movement?)

Java最小字符串运动？(Java minimum string movement?)

几天前我遇到了这样的问题：

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

1-交换字符串的两个连续字符2-交换字符串的第一个和最后一个字符

可以对任一字符串执行移动。 为获得两个相等的字符串，我们需要的最小移动次数是多少？ 输入格式和约束：输入的第一行和第二行包含两个字符串A和B.保证它们的字符相等的超集。 1 <= length（A）= length（B）<= 2000所有输入字符都在'a'和'z'之间

输出格式：将最小移动次数打印到输出的唯一行

样本输入：aab baa

样本输出：1

说明：交换字符串aab的第一个和最后一个字符以将其转换为baa。 这两个字符串现在相等。

我一直在尝试不同的算法但没有成功。 我总是做一些使他们平等但从不以最小的动作行事的事情。

编辑：我的伪代码是：

swap=>moves++ begin if(A[0]!=B[0]){ if(A[0]==B[length-1]){ swap(B[0], B[length-1]); } else if(B[0]==A[length-1]){ swap(A[0],A[length-1]); } } for(int i=0;i<A.length();i++){ if(A[i]==B[i]){ continue; } for(int j=i+1;j<A.length();j++){ if(A[i]==B[j]){ for(int k=j;k>i;k--){ swap(B[k],B[k-1]); } break; else if(B[i]=A[j]){ for(int k=j;k>i;k--){ swap(A[k],A[k-1]); } break; } }if(A==B){ break; }

对于一些不清楚的人，我的问题是如何让它发挥作用，任何想法，任何事情。 因为此刻，我很无能为力。

编辑：所以这是我迄今为止做的最好的主意：

public static void swap(char aChar, char bChar) { char cChar; cChar = aChar; aChar = bChar; bChar = cChar; } public static void main(String[] args) { int moves = 0; Scanner scanner = new Scanner(System.in); System.out.println("Enter the string A:"); while (!scanner.hasNext("[A-Za-z]+")) { System.out .println("Nope, that's not it! Enter the value from \"a\" to \"z\"." + "Enter your string A again!"); scanner.nextLine(); } String a = scanner.nextLine(); a.toLowerCase(); System.out.println("Enter the string B:"); while (!scanner.hasNext("[A-Za-z]+")) { System.out .println("Nope, that's not it! Enter the value from \"a\" to \"z\"." + "Enter your string B again!"); scanner.nextLine(); } String b = scanner.nextLine(); b.toLowerCase(); scanner.close(); char[] aChar = a.toCharArray(); char[] bChar = b.toCharArray(); if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) { if (aChar[0] != bChar[0]) { if (aChar[0] == bChar[bChar.length - 1]) { swap(bChar[0], bChar[bChar.length - 1]); moves++; } else if (bChar[0] == aChar[aChar.length - 1]) { swap(aChar[0], aChar[bChar.length - 1]); moves++; } } for (int i = 0; i < aChar.length; i++) { if (aChar[i] == bChar[i]) { continue; } for (int j = i + 1; j < aChar.length; j++) { if (aChar[i] == bChar[j]) { for (int k = j; k > i; k--) { swap(bChar[k], bChar[k - 1]); moves++; } break; } else if (bChar[i] == aChar[j]) { for (int k = j; k > i; k--) { swap(aChar[k], aChar[k - 1]); moves++; } break; } } if (aChar == bChar) { break; } } System.out.println("Minimum moves: " + moves); } } }

问题是它没有给出最小数量的运动。 可悲的是。 :)

将尝试更多的东西添加到这个代码，它可能会工作，但就目前而言，这就是我所拥有的......

Few days ago I got a problem which goes like this:

We have two strings A and B with the same super set of characters. We need to change these strings to obtain two equal strings. In each move we can perform one of the following operations:

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

A move can be performed on either string. What is the minimum number of moves that we need in order to obtain two equal strings? Input Format and Constraints: The first and the second line of the input contains two strings A and B. It is guaranteed that the superset their characters are equal. 1 <= length(A) = length(B) <= 2000 All the input characters are between 'a' and 'z'

Output Format: Print the minimum number of moves to the only line of the output

Sample input: aab baa

Sample output: 1

Explanation: Swap the first and last character of the string aab to convert it to baa. The two strings are now equal.

I have been trying different algorithms but without success. I always have been done something which makes them equal but never with minimum movement.

Edit: My pseudo code is:

swap=>moves++ begin if(A[0]!=B[0]){ if(A[0]==B[length-1]){ swap(B[0], B[length-1]); } else if(B[0]==A[length-1]){ swap(A[0],A[length-1]); } } for(int i=0;i<A.length();i++){ if(A[i]==B[i]){ continue; } for(int j=i+1;j<A.length();j++){ if(A[i]==B[j]){ for(int k=j;k>i;k--){ swap(B[k],B[k-1]); } break; else if(B[i]=A[j]){ for(int k=j;k>i;k--){ swap(A[k],A[k-1]); } break; } }if(A==B){ break; }

For some which is not clear about this, my question is how to make it work, any idea, anything. Because at the moment, I'm pretty clueless.

EDIT: So here is the best idea I did so far:

public static void swap(char aChar, char bChar) { char cChar; cChar = aChar; aChar = bChar; bChar = cChar; } public static void main(String[] args) { int moves = 0; Scanner scanner = new Scanner(System.in); System.out.println("Enter the string A:"); while (!scanner.hasNext("[A-Za-z]+")) { System.out .println("Nope, that's not it! Enter the value from \"a\" to \"z\"." + "Enter your string A again!"); scanner.nextLine(); } String a = scanner.nextLine(); a.toLowerCase(); System.out.println("Enter the string B:"); while (!scanner.hasNext("[A-Za-z]+")) { System.out .println("Nope, that's not it! Enter the value from \"a\" to \"z\"." + "Enter your string B again!"); scanner.nextLine(); } String b = scanner.nextLine(); b.toLowerCase(); scanner.close(); char[] aChar = a.toCharArray(); char[] bChar = b.toCharArray(); if ((a.length() >= 1 && a.length() <= 2000) && a.length() == b.length()) { if (aChar[0] != bChar[0]) { if (aChar[0] == bChar[bChar.length - 1]) { swap(bChar[0], bChar[bChar.length - 1]); moves++; } else if (bChar[0] == aChar[aChar.length - 1]) { swap(aChar[0], aChar[bChar.length - 1]); moves++; } } for (int i = 0; i < aChar.length; i++) { if (aChar[i] == bChar[i]) { continue; } for (int j = i + 1; j < aChar.length; j++) { if (aChar[i] == bChar[j]) { for (int k = j; k > i; k--) { swap(bChar[k], bChar[k - 1]); moves++; } break; } else if (bChar[i] == aChar[j]) { for (int k = j; k > i; k--) { swap(aChar[k], aChar[k - 1]); moves++; } break; } } if (aChar == bChar) { break; } } System.out.println("Minimum moves: " + moves); } } }

The problem is that it doesn't give the minimum number of movements. Sadly. :)

Will try some more stuff to add into this code and it might work, but for now, this is all I have...

最满意答案

public int findMinimumStringMovement() { int moves = 0; char[] aChar = a.toCharArray(); char[] bChar = b.toCharArray(); char cChar; if (aChar != bChar) { for (int i = 0; i < aChar.length; i++) { for (int j = i + 1; j < aChar.length; j++) { if (aChar[i] != bChar[i]) { /* * It checks if some character from the array of aChar * is same as other character from the array of B and if * it's j less then the length of the array. If it's * true, then swap the characters and count moves */ if (aChar[j] == bChar[i] && j < aChar.length) { for (int k = j; k > i; k--) { cChar = aChar[k]; aChar[k] = aChar[k - 1]; aChar[k - 1] = cChar; moves++; } /* * In other case, if the last character of array * aChar same as the some character of bChar and * vice versa, then we should check if the i is * equal to 0, in that case we swap 1st and last * character of array and count as 1 move else if i * value is less then the value of length of array * divided with 2 then it swaps that character to * the first one and then swaps with last and counts * the moves. */ } else if (aChar[aChar.length - 1] == bChar[i]) { if (i == 0) { cChar = aChar[aChar.length - 1]; aChar[aChar.length - 1] = aChar[i]; aChar[i] = cChar; moves++; } else if (i < (aChar.length - 1) / 2) { for (int k = i; k > 0; k--) { cChar = aChar[k]; aChar[k] = aChar[k - 1]; aChar[k - 1] = cChar; moves++; } cChar = aChar[i]; aChar[i] = aChar[aChar.length - 1]; aChar[aChar.length - 1] = cChar; } } else if (bChar[bChar.length - 1] == aChar[i]) { if (i == 0) { cChar = bChar[bChar.length - 1]; bChar[bChar.length - 1] = bChar[i]; bChar[i] = cChar; moves++; } else if (i < (aChar.length - 1) / 2) { for (int k = i; k > 0; k--) { cChar = aChar[k]; aChar[k] = aChar[k - 1]; aChar[k - 1] = cChar; moves++; } cChar = aChar[i]; aChar[i] = aChar[aChar.length - 1]; aChar[aChar.length - 1] = cChar; moves++; } /* * And the last case is if there is no other option, * then we asks if some characters in array with * positions i and j are different and if the j * value is less then length of the array and do the * swap. */ } else { if (aChar[j] != aChar[i] && j < aChar.length) { if (aChar[j] == bChar[j]) { cChar = bChar[j]; bChar[j] = bChar[i]; bChar[i] = cChar; moves++; } cChar = aChar[j]; aChar[j] = aChar[i]; aChar[i] = cChar; moves++; } else if (bChar[j] != bChar[i] && j < aChar.length) { if (aChar[j] == bChar[j] && aChar[j] != aChar[i]) { cChar = aChar[j]; aChar[j] = aChar[i]; aChar[i] = cChar; moves++; } cChar = bChar[j]; bChar[j] = bChar[i]; bChar[i] = cChar; moves++; } } /* * At the end, if arrays are equal, then it is done. */ if (aChar == bChar) { break; } } } } } return moves; }

我希望你会发现它有帮助的人。 很抱歉花了这么长时间才发布。 最好的祝福。

public int findMinimumStringMovement() { int moves = 0; char[] aChar = a.toCharArray(); char[] bChar = b.toCharArray(); char cChar; if (aChar != bChar) { for (int i = 0; i < aChar.length; i++) { for (int j = i + 1; j < aChar.length; j++) { if (aChar[i] != bChar[i]) { /* * It checks if some character from the array of aChar * is same as other character from the array of B and if * it's j less then the length of the array. If it's * true, then swap the characters and count moves */ if (aChar[j] == bChar[i] && j < aChar.length) { for (int k = j; k > i; k--) { cChar = aChar[k]; aChar[k] = aChar[k - 1]; aChar[k - 1] = cChar; moves++; } /* * In other case, if the last character of array * aChar same as the some character of bChar and * vice versa, then we should check if the i is * equal to 0, in that case we swap 1st and last * character of array and count as 1 move else if i * value is less then the value of length of array * divided with 2 then it swaps that character to * the first one and then swaps with last and counts * the moves. */ } else if (aChar[aChar.length - 1] == bChar[i]) { if (i == 0) { cChar = aChar[aChar.length - 1]; aChar[aChar.length - 1] = aChar[i]; aChar[i] = cChar; moves++; } else if (i < (aChar.length - 1) / 2) { for (int k = i; k > 0; k--) { cChar = aChar[k]; aChar[k] = aChar[k - 1]; aChar[k - 1] = cChar; moves++; } cChar = aChar[i]; aChar[i] = aChar[aChar.length - 1]; aChar[aChar.length - 1] = cChar; } } else if (bChar[bChar.length - 1] == aChar[i]) { if (i == 0) { cChar = bChar[bChar.length - 1]; bChar[bChar.length - 1] = bChar[i]; bChar[i] = cChar; moves++; } else if (i < (aChar.length - 1) / 2) { for (int k = i; k > 0; k--) { cChar = aChar[k]; aChar[k] = aChar[k - 1]; aChar[k - 1] = cChar; moves++; } cChar = aChar[i]; aChar[i] = aChar[aChar.length - 1]; aChar[aChar.length - 1] = cChar; moves++; } /* * And the last case is if there is no other option, * then we asks if some characters in array with * positions i and j are different and if the j * value is less then length of the array and do the * swap. */ } else { if (aChar[j] != aChar[i] && j < aChar.length) { if (aChar[j] == bChar[j]) { cChar = bChar[j]; bChar[j] = bChar[i]; bChar[i] = cChar; moves++; } cChar = aChar[j]; aChar[j] = aChar[i]; aChar[i] = cChar; moves++; } else if (bChar[j] != bChar[i] && j < aChar.length) { if (aChar[j] == bChar[j] && aChar[j] != aChar[i]) { cChar = aChar[j]; aChar[j] = aChar[i]; aChar[i] = cChar; moves++; } cChar = bChar[j]; bChar[j] = bChar[i]; bChar[i] = cChar; moves++; } } /* * At the end, if arrays are equal, then it is done. */ if (aChar == bChar) { break; } } } } } return moves; }

I hope that you'll find it helpfull guys. Sorry for taking so long to get it posted. Best regards.