class Solution {
public:
int kSimilarity(string s1, string s2) {
}
};
854. 相似度为 K 的字符串
字符串 s1 和 s2 是 k 相似 的(对于某些非负整数 k )，如果我们可以交换 s1 中两个字母的位置正好 k 次，使结果字符串等于 s2 。
给定两个字谜游戏 s1 和 s2 ，返回 s1 和 s2 与 k 相似 的最小 k 。
示例 1：
输入：s1 = "ab", s2 = "ba" 输出：1
示例 2：
输入：s1 = "abc", s2 = "bca" 输出：2
提示：
1 <= s1.length <= 20s2.length == s1.lengths1 和 s2 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母s2 是 s1 的一个字谜相似题目
原站题解
python3 解法, 执行用时: 60 ms, 内存消耗: 15.2 MB, 提交时间: 2022-09-21 10:18:01
class Solution:
'''
启发式搜索, A-Star 算法
'''
def kSimilarity(self, s1: str, s2: str) -> int:
def f(s):
cnt = sum(c != s2[i] for i, c in enumerate(s))
return (cnt + 1) >> 1
def next(s):
i = 0
while s[i] == s2[i]:
i += 1
res = []
for j in range(i + 1, n):
if s[j] == s2[i] and s[j] != s2[j]:
res.append(s2[: i + 1] + s[i + 1 : j] + s[i] + s[j + 1 :])
return res
q = [(f(s1), s1)]
dist = {s1: 0}
n = len(s1)
while 1:
_, s = heappop(q)
if s == s2:
return dist[s]
for nxt in next(s):
if nxt not in dist or dist[nxt] > dist[s] + 1:
dist[nxt] = dist[s] + 1
heappush(q, (dist[nxt] + f(nxt), nxt))
python3 解法, 执行用时: 72 ms, 内存消耗: 15.1 MB, 提交时间: 2022-09-21 10:17:19
class Solution:
'''
深度优先
'''
def kSimilarity(self, s1: str, s2: str) -> int:
s, t = [], []
for x, y in zip(s1, s2):
if x != y:
s.append(x)
t.append(y)
n = len(s)
if n == 0:
return 0
ans = n - 1
def dfs(i: int, cost: int) -> None:
nonlocal ans
if cost > ans:
return
while i < n and s[i] == t[i]:
i += 1
if i == n:
ans = min(ans, cost)
return
diff = sum(s[j] != t[j] for j in range(i, len(s)))
min_swap = (diff + 1) // 2
if cost + min_swap >= ans: # 当前状态的交换次数下限大于等于当前的最小交换次数
return
for j in range(i + 1, n):
if s[j] == t[i]:
s[i], s[j] = s[j], s[i]
dfs(i + 1, cost + 1)
s[i], s[j] = s[j], s[i]
dfs(0, 0)
return ans
python3 解法, 执行用时: 148 ms, 内存消耗: 16.3 MB, 提交时间: 2022-09-21 10:16:04
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