相似度为K的字符串.力扣854

Love The Way You Lie 2023-10-02 21:19 3阅读 0赞

### 一、题目描述 ###

![d0f7eaf36599478aa069deaf46218c4a.png][]

### 二、解题思路 ###

思路参考【瓜哇缪斯】

使用回溯法，每次对字符串进行字符交换时都会开辟一条新路线，当交换字符走完一跳路线后，需要进行回溯来走其他路线，求出交换次数，返回最小交换次数

下图以s1=“`bccaba`”，s2=“`abacbc`”为例，展示其中一种交换路线

![f2b7bde9456f4cc096b789654ae5b4d9.png][]

因为每次交换走完一跳路线之后都会进行回溯，所以有n中情况，但是没必要把所有的情况都执行一遍，在遍历时，如果当前交换次数已经大于最小交换次数，直接退出当前遍历。

![8d83ecff5ed04f5cbf0acb3c1f8229de.png][]

### 三、代码实现 ###

class Solution {
    
        int result = Integer.MAX_VALUE;
    
        public int kSimilarity(String s1, String s2) {
            return excute(s1.toCharArray(), s2.toCharArray(), 0, 0);
        }
    
        public int excute(char[] sc1, char[] sc2, int start, int current){
            //递归出口
            if(current >= result) return result;
            if(start == sc1.length - 1) return result = Math.min(result,current);
            for(int i = start; i < sc1.length; i++){
                if(sc1[i] != sc2[i]){
                    for(int j = i+1; j < sc2.length; j++){
                        //符合交换条件时，进行字符交换
                        if(sc2[j] == sc1[i] && sc2[j] != sc1[j]){
                            //交换
                            swap(sc2,i,j);
                            //每次调用方法交换次数+1
                            excute(sc1,sc2,i+1,current+1);
                            //回溯
                            swap(sc2,i,j);
                            //字符位置已经最优，跳出循环
                            if(sc2[i] == sc1[j]) break;
                        }
                    }
                    return result;
                }
            }
            return result = Math.min(result,current);
        }
    
        public void swap(char[] sc, int i, int j){
            char temp = sc[i];
            sc[i] = sc[j];
            sc[j] = temp;
        }
    }

[d0f7eaf36599478aa069deaf46218c4a.png]: https://img-blog.csdnimg.cn/d0f7eaf36599478aa069deaf46218c4a.png
[f2b7bde9456f4cc096b789654ae5b4d9.png]: https://img-blog.csdnimg.cn/f2b7bde9456f4cc096b789654ae5b4d9.png
[8d83ecff5ed04f5cbf0acb3c1f8229de.png]: https://img-blog.csdnimg.cn/8d83ecff5ed04f5cbf0acb3c1f8229de.png