854. K-Similar Strings

今天的题目是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：深搜 + 剪枝

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

int kSimilarity(string& s1, string& s2, int index) {
	// 减少递归次数
	while(index < s1.size() && s1[index] == s2[index]) index++;
	if (index >= s1.size()) return 0;
	if (index + 1 == s1.size()) return 1;
	auto key = s1 + s2;
	if (mem.count(key)) return mem[key];
	
	int res = s1.size();
	for (int j = index + 1; j < s1.size(); ++j) {
		// 剪枝1：在s1中找到与s2[index]相同的异构元素（s1,s2元素不同）
		if (s1[j] != s2[index] || s1[j] == s2[j]) continue;
		swap(s1[index], s1[j]);
		res = min(res, kSimilarity(s1, s2, index+1) + 1);
		swap(s1[index], s1[j]);
		// 剪枝2：如果交换后，两个位置的元素都同构了，则一定是最优交换
		if (s1[index] == s2[j]) break;
	}
	mem[key] = res;
	return res;
}