问题描述
给定两个等长字符串A和B，它们所含的字符个数及种类完全一样，问最少需要对A执行多少次交换字符才能使得A变成B？
分析
因为这个问题数据规模很小，只包含6种字符、A和B的长度都不超过20，所以暴力+适当剪枝的思路就能够通过。
首先对于A[i]B[i]的部分，完全不需要做任何处理；
其次，对于A[i]!=B[i]的部分，显然需要找A[j]来跟A[i]进行交换，A[j]满足A[j]B[i]。在这个过程中，如果A[i]==B[j]，那自然是“意外之喜”，“一箭双雕”，“一石二鸟”。可以很自信的想：如果能够一箭双雕，必然是最优策略。但是，如果没有“一箭双雕”，那就只能逐个尝试寻找最优的 j 了。假设就选择了j，交换完后得到新的字符串A'，可以递归调用求solve(A’，B)。
在这个递归过程中，因为B是不变的，这个函数只要A确定，返回值就定下来了。所以可以用备忘录方法（记忆化搜索）来加速递归。
站在更宏观的角度考虑这个问题，把每个A字符串当做结点，每一次swap操作会形成新的结点并添加一条边，以上递归的过程相当于深度优先搜索。如果改写成广度优先搜索，运行效率必定能够提高。
站在更宏观的角度考虑这个问题，这是一个很艰难的图论问题。问题等价于寻找有向图的边的一个覆盖，使得每一个子集都是环，要使环数最大。这个问题似乎是个NP问题。
但是贪心的方式足以通过此题。
贪心法则如下：
- 选择每个顶点的最小环构成一个最小环集合，对此集合执行去重操作。
- 如果环集合中存在结点数为1的环，必然选择之。
- 如果环集合中存在结点数为2的环，必然选择之。
- 否则，执行以下步骤。
- 对于这个环集合，统计图中边的使用次数。
- 对每个环，求它边的平均使用次数作为这个环的value。
- 优先消去value最小的环
这个问题等价于：
给定一个可以包含重复元素的数组，最少需要执行多少次swap操作，才能使数组变得有序。
C++递归写法
class Solution {
public:
unordered_map<string,int> mp;
int kSimilarity(string A, string B) {
if(A<B) return kSimilarity(B,A);
if(mp[A+B]) return mp[A+B];
int i=0;
while(i<A.size() && A[i]==B[i]) i++;
if(i==A.size()) return 0;
int j=i+1;
vector<int> pos;
while(j<A.size()){
if(A[j]==B[i]){
if(A[i]==B[j]){
pos.clear();
pos.push_back(j);
break;
}
pos.push_back(j);
};
j++;
}
int res=INT_MAX;
for(int p:pos){
swap(A[i],A[p]);
res=min(res,kSimilarity(A.substr(i+1),B.substr(i+1)));
swap(A[i],A[p]);
}
return mp[A+B]=res+1;
}
};
Java非递归写法
class Solution {
public int kSimilarity(String A, String B) {
if (A.equals(B)) return 0;
Set<String> vis= new HashSet<>();
Queue<String> q= new LinkedList<>();
q.add(A);
vis.add(A);
int res=0;
while(!q.isEmpty()){
res++;
for (int sz=q.size(); sz>0; sz--){
String s= q.poll();
int i=0;
while (s.charAt(i)==B.charAt(i)) i++;
for (int j=i+1; j<s.length(); j++){
if (s.charAt(j)==B.charAt(j) || s.charAt(i)!=B.charAt(j) ) continue;
String temp= swap(s, i, j);
if (temp.equals(B)) return res;
if (vis.add(temp)) q.add(temp);
}
}
}
return res;
}
public String swap(String s, int i, int j){
char[] ca=s.toCharArray();
char temp=ca[i];
ca[i]=ca[j];
ca[j]=temp;
return new String(ca);
}
}
Java贪心法
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;
import java.util.stream.Collectors;
class Solution {
/**
* 构图，构完图之后，两个字符串就可以丢掉了
*/
int[][] buildGraph(char[] a, char[] b) {
TreeMap<Character, Integer> ma = new TreeMap<>();
for (char i : a) {
if (!ma.containsKey(i)) {
ma.put(i, ma.size());
}
}
for (char j : b) {
if (!ma.containsKey(j)) {
ma.put(j, ma.size());
}
}
int g[][] = new int[ma.size()][ma.size()];
for (int i = 0; i < a.length; i++) {
int from = ma.get(b[i]), to = ma.get(a[i]);
g[from][to] += 1;
}
return g;
}
/**
* 计算结点node的出度
*/
int outEdge(int node, int[][] g) {
return Arrays.stream(g[node]).sum();
}
int[][] copyGraph(int[][] g) {
int[][] a = new int[g.length][g.length];
for (int i = 0; i < g.length; i++) {
for (int j = 0; j < g.length; j++) {
a[i][j] = g[i][j];
}
}
return a;
}
/**
* 寻找node结点所在的最小环
*/
List<List<Integer>> findMinRingOf(int node, int[][] g) {
g = copyGraph(g);
List<List<Integer>> rings = new LinkedList<>();
while (outEdge(node, g) > 0) {
int[] prev = new int[g.length];//记录最小环的路径
Arrays.fill(prev, -1);
Queue<Integer> q = new LinkedList<>();
q.add(node);
out:
while (!q.isEmpty()) {
Integer i = q.poll();
for (int j = 0; j < g[i].length; j++) {
if (g[i][j] > 0) {
if (prev[j] != -1) continue;//已经访问过了就不再访问了
prev[j] = i;
q.add(j);//准备扩展j结点
if (j == node) {//找到了
break out;
}
}
}
}
ArrayList<Integer> a = new ArrayList<>(g.length);
a.add(node);
int now = node;
while (true) {
int next = prev[now];
if (next == node) break;
a.add(next);
now = next;
}
//翻转数组
for (int i = 0; i < a.size() >> 1; i++) {
int temp = a.get(i);
a.set(i, a.get(a.size() - 1 - i));
a.set(a.size() - 1 - i, temp);
}
if (rings.isEmpty() || rings.get(0).size() == a.size()) {
rings.add(a);
} else {
break;
}
removeRing(a, g);
}
return rings;
}
/**
* 用完一个环之后，把环删除
*/
void removeRing(List<Integer> ring, int[][] g) {
for (int i = 0; i < ring.size(); i++) {
g[ring.get(i)][(ring.get((i + 1) % ring.size()))]--;
}
}
/**
* 贪心寻找图中最优环
*/
List<Integer> findMinRing(int[][] g) {
List<List<Integer>> rings = new LinkedList<>();//全部环构成的集合
for (int i = 0; i < g.length; i++) {
if (outEdge(i, g) > 0) {
List<List<Integer>> r = findMinRingOf(i, g);
rings.addAll(r);
}
}
//去重
Set<String> had = new TreeSet<>();
LinkedList<List<Integer>> uniqRings = new LinkedList<>();
for (List<Integer> ring : rings) {
String k = ring.stream().sorted().map(x -> x + "").collect(Collectors.joining(","));
if (!had.contains(k)) {
had.add(k);
uniqRings.add(ring);
}
}
rings = uniqRings;
//统计每条边的使用次数
double[][] use = new double[g.length][g.length];
for (List<Integer> ring : rings) {
for (int j = 0; j < ring.size(); j++) {
use[ring.get(j)][ring.get((j + 1) % ring.size())]++;
}
}
rings.sort(Comparator.comparing(x -> {
if (x.size() == 1) return -1.0;//优先级最高
if (x.size() == 2) return 0.0;//优先级次高
double s = 0;
for (int i = 0; i < x.size(); i++) {
s += use[x.get(i)][x.get((i + 1) % x.size())];
}
s /= x.size();
return s;
}));
if (rings.size() == 0) return null;
return rings.get(0);
}
public int kSimilarity(String A, String B) {
char[] a = A.toCharArray(), b = B.toCharArray();
int[][] g = buildGraph(a, b);
int N = a.length;
while (true) {
List<Integer> ring = findMinRing(g);
if (ring == null) break;
N--;
removeRing(ring, g);
}
return N;
}
public static void main(String[] args) {
try {
Scanner cin = new Scanner(new FileInputStream("in.txt"));
System.out.println(new Solution().kSimilarity(cin.next(), cin.next()));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
}