Interview Question
Country: India
Nice one!
However, it would be better to check validity of any swap before adding to queues, because a bad swap would not be a part of a shortest path. Doing this would also give us a much smaller search space, hence a better time complexity.
We can also use A* instead of BFS to solve this a bit faster.
Hi,
This is an interesting problem, which is one instance of "genome sorting/re-arranging" problem. The genome sorting problem considers other kind of operations like reversal, translocation, transposition... as well. This genome sorting problem is NP-hard; people often use break-point graph to tackle it with approximation...
I doubt that there is polynomial time algorithm for this instance (??).
Back to this swapping problem:
By swapping each character to correct position, the maximum number of swaps is n-1.
BFS in this case will find optimal solution. However, its searching space is exponential. Two-way BFS is a bit better, but still fails for long string (?).
I also think A* can do better than naive BFS in this case.
I wonder if a guided BFS can do well here. My idea is that, we do BFS on the original string, using the target string to guide. That is, for each swap, I try to find a swap that moves closer to the target. Thus, I will swap so that after swaping, at least one more position is correct.
However, I am not clear if it doesn't miss any optimal solution.
You can do this in O(n log n) time using a modified mergesort.
Thought behind this:
Mismatches in the two strings can actually be thought of as array inversions (elements out of order in an ordered sequence)
let s1 = kamal
let s2 = amalk
If we assume that s1 is the "correct" ordering, we can create an array P that holds a mapping from a character in s2 to its position in s1.
# correct ordering
0 1 2 3 4
k a m a l
# ordering of s2
1 2 3 4 0
a m a l k
So, P = [1, 2, 3, 4, 0]
We can see the inversions of P by drawing intersection lines between the elements of P and the correct ordering:
0 1 2 3 4
\/_/_ /_/
/ / / / |
1 2 3 4 0
0 ------ 1
1----/ ------ 2
2----/ ------ 3
3----/ ------ 4
4----/ 0
(assume a line between 0 and 0, ascii art is not the best medium)
Counting the number of intersections will tell use the number of elements "out of order", noting that "out of order" in this case means distance of s2 from s1 in swaps.
To implement inversion counting, you can modify the merge_sort and merge steps of the standard merge_sort algorithm:
#include <stdio.h>
int merge_sort(int[],int,int);
int merge(int[],int,int,int);
int main(int argc, char ** argv) {
int array[] = { 1, 2, 3, 4, 0 };
int array_size = sizeof(array)/sizeof(array[0]);
int inversions = merge_sort(array, 0, array_size - 1);
printf("Found %d inversions\n", inversions);
return 0;
}
int merge_sort(int a[], int start, int end) {
if ( end > start ) {
int mid = start + (end - start) / 2;
int x = merge_sort(a, start, mid);
int y = merge_sort(a, mid + 1, end);
int z = merge(a, start, mid, end);
return x + y + z;
}
return 0;
}
int merge(int a[], int start, int mid, int end) {
int l = start, r = mid + 1;
int i = 0;
int temp[end - start + 1];
int splitInversionCount = 0;
while ( l <= mid && r <= end ) {
if ( a[l] < a[r] ) {
temp[i++] = a[l++];
}
else {
splitInversionCount += mid - l + 1;
temp[i++] = a[r++];
}
}
// copy whichever half of the array remains
while ( l <= mid ) {
temp[i++] = a[l++];
}
while ( r <= end ) {
temp[i++] = a[r++];
}
// copy temp back into a
int k;
for(k = 0; k < i; k++) {
a[k + start] = temp[k];
}
return splitInversionCount;
}
There might be a few other optimizations, none that come to mind though.
Inversion counting does not give the correct answer. Correct answer is 3 for the example in the statement; however, there are 4 inversions.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class TransformStringInMinimumSwaps {
public static String transform(String a, String b) {
if (a == null || b == null || a.length() != b.length()) {
return null;
}
// Establish char to position relationship in the targeted layout.
Map<Character, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i < b.length(); ++i) {
if (b.charAt(i) != a.charAt(i)) {
ArrayList<Integer> temp = map.get(b.charAt(i));
if (temp == null) {
temp = new ArrayList<Integer>();
map.put(b.charAt(i), temp);
}
temp.add(i);
}
}
// Figure out where each element to be relocated.
int[] pos = new int[a.length()];
for (int i = 0; i < a.length(); ++i) {
if (a.charAt(i) == b.charAt(i)) {
pos[i] = i;
} else {
ArrayList<Integer> temp = map.get(a.charAt(i));
pos[i] = temp.get(0);
temp.remove(0);
if (temp.size() == 0) {
map.remove(temp);
}
}
}
// Do the relocation
char[] chr = a.toCharArray();
for (int i = 0; i < chr.length; ++i) {
while (pos[i] != i) {
char c = chr[i];
chr[i] = chr[pos[i]];
chr[pos[i]] = c;
int t = pos[pos[i]];
pos[pos[i]] = pos[i];
pos[i] = t;
}
}
return new String(chr);
}
public static void main(String[] args) {
String a = "kamal";
String b = "amlak";
System.out.println("Origin: " + a);
System.out.println("Target: " + b);
System.out.println("Result: " + transform(a, b));
}
}
def getMin(fr="", to=""):
parent = {fr:None}
level = {fr:0}
l=1
frontier = [fr]
while(frontier):
next = []
for i in frontier:
temp = i
length = len(i)
for x in range(length):
for y in range(x+1,length):
temp2 = list(temp)
temp2[x], temp2[y] = temp2[y], temp2[x]
temp2 = ''.join(temp2)
if (temp2 not in frontier) and (temp2 not in parent):
parent[temp2] = i
level[temp2] = l
next.append(temp2)
#print(level)
#print("")
#print("")
frontier = next
l+=1
return level
def main():
level = getMin("apple", "eaplp")
print(level["eaplp"])
if __name__ == '__main__':
main()
Will it work? It's working on some test cases. How can I optimize this?
What about bidirectional BFS:
- uuuouou May 14, 2014