word distance

两个anagram string S 和 P,定义两个操作:

1)相邻的character swap算一次操作
2)第一个character 和最后一个character swap算一次操作

问从S变到P的最小操作数。

We can look at this problem like a sorting problem, because if sort to anagrams, we will have the same string. if we mark each char in S to a number from 1 to n, then the question becomes what is the minimum swap we need to sort P? (Lets ignore the circular pattern first).

To count number of inversions, we have (modified) merge sort that runs nlogn time.

class solution {
	public int countInv(int [] a, int start, int end) {
		if (start >= end)
			return 0;
		int mid = (start + end)/2;
		int inv1 = countInv(a, start, mid);
		int inv2 = countInv(a, mid+1, end);
		int p1 = start;
		int p2 = mid+1;
		int count = 0;
		while(p2 <= end && p1 <= mid) {
			if (a[p1] > a[p2]) {
				p2++;
				count++;
			}
			else {
				p1++;
			}
		}
		count += Math.max(0, p2 - end);
		return count + inv1 + inv2;
	}
}

But to count number of swaps, we need bubble sort, and we need to consider the circular conditions to decide we bubble to left or right depending on the current position. That way we get the number of swaps.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s