Leetcode力扣秋招刷题路-0854-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode力扣秋招刷题路-0854。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

854. 相似度为 K 的字符串

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

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

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

示例 2：
输入：s1 = “abc”, s2 = “bca”
输出：2

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

思路：从最左边的i=0位置开始，对比A和B的字符，如果当前位置i的字符不相等，就在B中后面字符i+1及后面位置中找和当前A中i位置相等的字符，找到后就进行交换位置，然后递归进去从i+1的位置开始直到最末尾位置时记录当前交换次数，具体看代码，非常直观文章来源地址https://www.toymoban.com/news/detail-431082.html

class Solution {
    int minCount = Integer.MAX_VALUE;
    public int kSimilarity(String A, String B) {
        int len = A.length();

        char[] recordA = new char[len];
        char[] recordB = new char[len];

        for (int i = 0; i < len; i++){
            recordA[i] = A.charAt(i);
            recordB[i] = B.charAt(i);
        }

        doSelect(recordA, recordB, len, 0, 0);

        return minCount;
    }

    private void doSelect(char[] recordA, char[] recordB, int len, int curCount, int curIndex){
        if (curCount > minCount) return; // 当前次数已经超过当前最小次数，则直接返回不必要进行递归了

        if (curIndex == len - 1){
            if (curCount < minCount) minCount = curCount;
            return;
        }

        int i = curIndex;
        for (; i < len; i++){
            if (recordA[i] == recordB[i]) continue; // 当前的元素相等的话，就直接遍历下一个

            // 不相等，进行从recordB后续的字符中找与当前A中相等的字符进行替换
            char aCurChar = recordA[i];
            int k = i + 1;
            for (; k < len; k++){
                if (aCurChar == recordB[k]){ // 找到其中一个与aCurChar相等的字符，则进行位置交换
                    swap(recordB, i, k);
                    doSelect(recordA, recordB, len, curCount + 1, i + 1);
                    swap(recordB, i, k); // 替换回来
                }
            }
            return;
        }

        if (i == len){
            if (curCount < minCount) minCount = curCount;
        }
    }

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

到了这里，关于Leetcode力扣秋招刷题路-0854的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！