辽宁省建设厅网站中级职称公示安卓程序开发

题目链接

相似度为 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;}
}

关键点

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