Code & Func

今天的题目是854. K-Similar Strings

对于某些非负整数 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 的一个字母异位词

解法1：深搜 + 剪枝

1
unordered_map<string, int> mem; // 感觉好像没啥用
2
int kSimilarity(string s1, string s2) {
3
  return kSimilarity(s1, s2, 0);
4
}
5

6
int kSimilarity(string& s1, string& s2, int index) {
7
  // 减少递归次数
8
  while(index < s1.size() && s1[index] == s2[index]) index++;
9
  if (index >= s1.size()) return 0;
10
  if (index + 1 == s1.size()) return 1;
11
  auto key = s1 + s2;
12
  if (mem.count(key)) return mem[key];
13

14
  int res = s1.size();
15
  for (int j = index + 1; j < s1.size(); ++j) {
11 collapsed lines
16
    // 剪枝1：在s1中找到与s2[index]相同的异构元素（s1,s2元素不同）
17
    if (s1[j] != s2[index] || s1[j] == s2[j]) continue;
18
    swap(s1[index], s1[j]);
19
    res = min(res, kSimilarity(s1, s2, index+1) + 1);
20
    swap(s1[index], s1[j]);
21
    // 剪枝2：如果交换后，两个位置的元素都同构了，则一定是最优交换
22
    if (s1[index] == s2[j]) break;
23
  }
24
  mem[key] = res;
25
  return res;
26
}