0854._K-Similar_Strings.md

854. K-Similar Strings

题目: https://leetcode.com/problems/k-similar-strings

难度: Hard

题意：

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;
    }
}