相似度为 K 的字符串

题目链接

相似度为 K 的字符串

题目描述

注意

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

解答思路

• 可以深度优先遍历交换字母使得s1和s2尽可能接近，基本思路是：设定一个指针idx指向s1和s2的相同位置，如果此时指针处的字母不同（此时前面的字母已经相同），则需要将此处的字母与后面的字母进行交换，使用该位置处的字母相同后再继续深度优先遍历，深搜过后需要进行回溯，防止对其他深搜过程造成影响
• 为了降低时间复杂度，还要注意进行剪枝
  • 在进入本次dfs时，如果交换次数过多，则可以直接进行剪枝
  • 在寻找后面的字母对idx处字母进行交换时，如果相似度仍然相同（arr1[j] != arr2[j]），则可以进行剪枝
  • 在寻找后面的字母对idx处字母进行交换时，如果如果交换后对应i位和j位处的字母都相等，则可以认为已是最优交换（一次交换相似度最多减少2），可以进行剪枝

代码

class Solution {
    int n;
    int res;
    
    public int kSimilarity(String s1, String s2) {
        n = s1.length();
        res = Integer.MAX_VALUE;
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        dfs(arr1, arr2, 0, 0);
        return res;
    }

    public void dfs(char[] arr1, char[] arr2, int idx, int count) {
        // 交换次数过多，直接剪枝
        if (count >= res) {
            return;
        }
        for (int i = idx; i < n; i++) {
            if (arr1[i] != arr2[i]) {
                for (int j = i + 1; j < n; j++) {
                    // 贪心选择->保证交换后相似度更低
                    if (arr1[j] == arr2[i] && arr1[j] != arr2[j]) {
                        swap(arr1, i, j);
                        dfs(arr1, arr2, i + 1, count + 1);
                        // 回溯
                        swap(arr1, i, j);
                        // 贪心选择->如果交换后对应i位和j位处的字母都相等，则可以认为已是最优交换
                        if (arr1[i] == arr2[j]) {
                            break;
                        }
                    }
                }
                return;
            }
        }
        res = Math.min(res, count);
    }

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

关键点

• 深度优先遍历的思想
• 注意剪枝的情况

原文地址：https://blog.csdn.net/weixin_51628158/article/details/126993481

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！