Daily LeetCode – day0054 0854. K-Similar Strings

// 0854. K-Similar Strings
class Solution {
    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) return 0;
        int moves = 0;
        int len = s1.length();
        Queue<String> queue = new LinkedList<>();
        queue.offer(s1);
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add(s1);
        int newShortest = closer(s1, s2);
        int oldShortest = newShortest;
        while (!queue.isEmpty()) {
            ++moves;
            oldShortest = newShortest;
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; ++i) {
                String front = queue.poll();
                if (closer(front, s2) == oldShortest) {
                    for (int j = 0; j < len - 1; ++j) {
                        for (int k = j + 1; k < len; ++k) {
                            String swapped = swap(front, j, k);
                            if (!hashSet.contains(swapped)) {
                                if (s2.equals(swapped)) {
                                    return moves;
                                }
                                int distance = closer(swapped, s2);
                                if (distance < oldShortest) {
                                    if (distance <= newShortest) {
                                        newShortest = distance;
                                        hashSet.add(swapped);
                                        queue.offer(swapped);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

    String swap(String origin, int i1, int i2) {
        char[] charArray = origin.toCharArray();
        char temp = charArray[i1];
        charArray[i1] = charArray[i2];
        charArray[i2] = temp;
        return new String(charArray);
    }

    int closer(String s, String s2) {
        int ret = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) != s2.charAt(i)) ++ret;
        }
        return ret;
    }
}

学习笔记：
这道题是困难题，用的知识点可以中等就解决，使用宽度优先搜索。
但是简单的宽度优先搜索越来越多，就肯定超时。
所以需要剪枝，剪枝的方案就是：能一次交换就完成2个字符的，就不完成1个。
所以我写了个closer函数，判断当前字符串到结果的距离。必须越来越近。
越来越近还是会超时的，必须要一次进两步的时候就进两步。
把交换完成2个字符的放进队列，但这样会出现bug，那就是最后几步只能一步步前进的情况。
所以还是要记录一个上一轮最短距离和本轮新最短距离的变量，如果发现这一轮有缩短2步的，那么之后只缩短1步的情况就不加队列了。并且再新的一轮中，要把上一轮前期那些只缩短1步的垃圾情况过滤，不让他们搞循环浪费更多时间。