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

### Like this:

Like Loading...

*Related*