# 854. K-Similar Strings

### 854. K-Similar Strings

1. 给定两个字符串，问最少要交换多少次，使得A变成了B，A和B里面的字母都是a-f

• 将字符串A到字符串B的变换看成图，那么这张图就是一个一个环构成的。环上，交换的次数等于环的长度-1，所以这个题目变成了，将图拆成环，使环的个数最大
• 后面就是纯搜索，注意状态合并。状态定义为，当前图的状态（6*6的矩阵），然后在图上寻找所有的可行环，分别去掉，转成下一个状态

class Solution {
private class State implements Comparable<State> {
int[] a;
int total;

State() {
a = new int[6];
Arrays.fill(a, 0);
total = 0;
}

State(int[] a, int total) {
this.a = Arrays.copyOf(a, a.length);
this.total = total;
}

private int get(int x, int y) {
return (a[x] >> (y * 4)) & 15;
}

private void minus(int x, int y) {
a[x] -= 1 << (y * 4);
total--;
}

private void add(int x, int y) {
a[x] += 1 << (y * 4);
total++;
}

@Override
public int compareTo(State o) {
if (Integer.compare(total, o.total) == 0) {
for (int i = 0;i < 6;i++) {
if (Integer.compare(a[i], o.a[i]) != 0) {
return Integer.compare(a[i], o.a[i]);
}
}
return 0;
} else {
return -Integer.compare(total, o.total);
}
}
}

private void extand(boolean[] flag, int[] pos, TreeMap<State, Integer> stateMap, State current, int idx) {
if (current.get(pos[idx - 1], pos[0]) != 0) {
State next = new State(current.a, current.total);
for (int i = 0;i < idx - 1;i++) {
next.minus(pos[i], pos[i + 1]);
}
next.minus(pos[idx - 1], pos[0]);
int value = stateMap.get(current);
value += idx - 1;
if (stateMap.containsKey(next)) {
value = value < stateMap.get(next) ? value : stateMap.get(next);
stateMap.put(next, value);
} else {
stateMap.put(next, value);
}
}

if (idx == 6) {
return;
}
for (int i = 0;i < 6;i++) {
if (!flag[i] && current.get(pos[idx - 1], i) != 0) {
flag[i] = true;
pos[idx] = i;
extand(flag, pos, stateMap, current, idx + 1);
flag[i] = false;
}
}
}

private void solve(TreeMap<State, Integer> stateMap, State current) {
boolean[] flag = new boolean[6];
Arrays.fill(flag, false);
int[] pos = new int[6];
int min = -1;
for (int i = 0;i < 6;i++) {
if (current.a[i] != 0) {
min = i;
break;
}
}
if (min == -1) {
return;
}
flag[min] = true;
pos[0] = min;
extand(flag, pos, stateMap, current, 1);
}

public int kSimilarity(String A, String B) {
TreeMap<State, Integer> stateMap = new TreeMap<State, Integer>();
State start = new State();
for (int i = 0;i < A.length();i++) {
if (A.charAt(i) != B.charAt(i)) {
start.add(A.charAt(i) - 'a', B.charAt(i) - 'a');
}
}
int ret = 0x3fffffff;
stateMap.put(start, 0);

while (!stateMap.isEmpty()) {
State current = stateMap.firstKey();
if (current.total == 0) {
ret = ret < stateMap.get(current) ? ret : stateMap.get(current);
} else {
solve(stateMap, current);
}
stateMap.remove(current);
}
return ret;
}
}