LeetCode每日一题——854. 相似度为 K 的字符串

LeetCode每日一题系列

题目：854. 相似度为 K 的字符串
难度：困难

---

---

题目

对于某些非负整数 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、自己想的是无剪枝和去重的暴力DFS和BFS搜索，但是结果都超时了
2、参考了官方题解，找到了对BFS剪枝和去重的内容
去重：用哈希表记录每次计算时得到的中间状态，当通过交换时发现当前状态已经计算过，则此时我们可以直接跳过该状态。
剪枝：我们只考虑s1[j] = s2[i] != s2[j]的情况，因为第i位后面如果第j位s1和s2已经相等，我们再做替换是多余的操作。

题解

暴力DFS超时代码

class Solution:
    def kSimilarity(self, A, B):
        ans = []
        s1 = list(A)
        def process(s1,index,s):
            if ''.join(s1) == B:
                ans.append(s)
                return
            for i in range(index, len(s1)):
                for j in range(i+1, len(s1)):
                    s1[i],s1[j] = s1[j], s1[i]
                    process(s1, i+1, s+1)
                    s1[i],s1[j] = s1[j], s1[i]
        process(s1, 0, 0)
        return min(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

BFS+剪枝+去重

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
    	# 已走步长
        step, n = 0, len(s1)
        # 列表模拟队列，哈希表去重
        q, vis = [(s1, 0)], {s1}
        while True:
            tmp = q
            q = []
            # 遍历队列
            for s, i in tmp:
                if s == s2:
                    return step
                while i < n and s[i] == s2[i]:
                    i += 1
                for j in range(i + 1, n):
                    if s[j] == s2[i] != s2[j]:  # 剪枝，只在 s[j] != s2[j] 时去交换
                        t = list(s)
                        t[i], t[j] = t[j], t[i]
                        t = ''.join(t)
                        # 判重
                        if t not in vis:
                            vis.add(t)
                            q.append((t, i + 1))
            step += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25