854. 相似度为 K 的字符串

一、题目描述

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

输入：s1 = “ab”, s2 = “ba”
输出：1

提示：

• 1 <= s1.length <= 20
• s2.length == s1.length
• s1 和 s2 只包含集合 {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’} 中的小写字母
• s2 是 s1 的一个字母异位词

二、解题思路

查找交换的所有可能情况，可以采用回溯法。

• 每次交换，至少把 1 个字符换到正确的位置

这样子做的话，交换次数最多 n - 1 次。

因为 n - 1 次交换之后，前 n - 1 个字符都已经对上了，那最后一个肯定也对上了。

• 最优的交换是，交换后的 2 个字符的位置都是正确的

可利用最优交换进行快速剪枝。另外，

• 如果当前交换次数，比之前最小的交换次数还大了，此时可以直接剪枝

三、复杂度分析

不分析时空复杂度。

四、参考代码

int ans = Integer.MAX_VALUE;

private int kSimilarity(String s1, String s2) {
    backtrace(s1.toCharArray(), s2.toCharArray(), 0, 0);
    return ans;
}

/**
 * 思路：回溯法，每次换位都确保有 1 位能够在正确位置上，从左往右逐个换位
 * <p>
 * 执行耗时:21 ms,击败了81.61% 的Java用户
 * 内存消耗:39.1 MB,击败了98.85% 的Java用户
 */
private void backtrace(char[] s1, char[] s2, int index, int cnt) {
    // 快速剪枝，交换次数比最小值大了
    if (cnt >= ans) {
        return;
    }

    // 2 个字符串已经相等了
    if (index >= s1.length) {
        ans = cnt;
        return;
    }

    // 当前位相同，无需交换，进行下一步
    if (s1[index] == s2[index]) {
        backtrace(s1, s2, index + 1, cnt);
        return;
    }

    int n = s1.length;
    for (int i = index + 1; i < n; i++) {
        // 回溯交换，把 index 的字符换位到 2 者相等
        if (s1[i] == s2[index] && s1[i] != s2[i]) {
            swap(s1, index, i);
            backtrace(s1, s2, index + 1, cnt + 1);
            swap(s1, i, index);

            /*
             * 这个地方的剪枝非常重要
             * 执行耗时:2 ms,击败了92.53% 的Java用户
             * 内存消耗:39.2 MB,击败了93.10% 的Java用户
             */
             // 交换后 2 个位置都相等，已经是最优解
            if (s1[index] == s2[i]) {
                break;
            }
        }
    }
}

private void swap(char[] sc, int i, int j) {
    char temp = sc[i];
    sc[i] = sc[j];
    sc[j] = temp;
}