CareerCup

What about bidirectional BFS:

#include <cstring>
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

bool containSameCharacters(const string& a, const string& b)
{
	if(a.size() != b.size()) return false;
	
	int count[256], i, len = a.size();
	memset(count, 0, sizeof(count));
	for(i = 0; i < len; ++i) ++count[a[i]];
	for(i = 0; i < len; ++i){
		if(--count[b[i]] < 0) return false;
	}
	return true;
}
int getMinimumSwaps(const string& from, const string& to)
{
	if(!containSameCharacters(from, to)) return -1;
	if(from == to) return 0;

	unordered_map<string, int> fromMap, toMap;//record state already visited and 
											  //how many swaps need to transfrom into this state
	queue<string> fromQueue, toQueue;//states queue
	int level = 1;					 //how many swaps has been done

	string tmp;
	int i, j, k, n, len = from.size();
	unordered_map<string, int>::iterator iter;
	//initialize
	fromQueue.push(from);
	fromMap[from] = 0;
	toQueue.push(to);
	toMap[to] = 0;
	//binary BFS
	for(; !fromQueue.empty() && !toQueue.empty(); ++level){
		//extend state in fromQueue
		for(i = 0, n = fromQueue.size(); i < n; ++i){
			tmp = fromQueue.front();
			fromQueue.pop();
			for(j = 0; j < len; ++j){
				for(k = j+1; k < len; ++k){
					swap(tmp[j], tmp[k]);//try to swap tmp[j] with tmp[k]
					iter = toMap.find(tmp);//check if this state has been visited by 'to'
					if(iter != toMap.end()){
						cout << "fromMap["<< tmp << "]= " << level << endl;
						cout << "toMap[" << tmp << "]= " << iter->second << endl;
						return level + iter->second;
					}
					else if(fromMap.find(tmp) == fromMap.end()){//check if this state has been visited by 'from'
						fromQueue.push(tmp);
						fromMap[tmp] = level;
					}
					swap(tmp[j], tmp[k]);
				}
			}
		}
		//extend state in toQueue
		for(i = 0, n = toQueue.size(); i < n; ++i){
			tmp = toQueue.front();
			toQueue.pop();
			for(j = 0; j < len; ++j){
				for(k = j+1; k < len; ++k){
					swap(tmp[j], tmp[k]);//try to swap tmp[j] with tmp[k]
					iter = fromMap.find(tmp);//check if this state has been visited by 'from'
					if(iter != fromMap.end()){
						cout << "toMap[" << tmp << "]= " << level << endl;
						cout << "fromMap["<< tmp << "]= " << iter->second << endl;
						return level + iter->second;
					}
					else if(toMap.find(tmp) == toMap.end()){//check if this state has been visited by 'to'
						toQueue.push(tmp);
						toMap[tmp] = level;
					}
					swap(tmp[j], tmp[k]);
				}
			}
		}
	}

	return -1;//actually it never reaches here
}

int main()
{
	cout << getMinimumSwaps("kamal", "amalk");
	return 0;
}

Can we swap arbitrary two characters or just adjacent ones?

My Algo goes here

1> Loop both string one character at a time.
2> if character mismatch {
if(map is not empty && map.contains(character)) {
swap the element to the index and remove that element from the map
} else
put that character and the index of mismatch in a Map.
}

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.

This is a well known edit distance problem

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?

1
kamal -> akmal