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...
