0854：相似度为 K 的字符串（2377 分）

2018-06-17 约 311 字预计阅读 1 分钟次阅读

力扣第 89 场周赛第 4 题

题目

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

相似问题：

0765：情侣牵手（1999 分）

分析

按 s1 最后一个字符和哪个位置交换即可递归
可以先把 s1 和 s2 相同的部分去掉，节省时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        @cache
        def dfs(s1,s2):
            if not s1:
                return 0
            if s1[0]==s2[0]:
                return dfs(s1[1:],s2[1:])
            res = inf
            for i in range(1,len(s2)):
                if s2[i]==s1[0]:
                    res = min(res, 1+dfs(s1[1:],s2[1:i]+s2[0]+s2[i+1:]))
            return res
        A,B = [],[]
        for a,b in zip(s1,s2):
            if a!=b:
                A.append(a)
                B.append(b)
        s1,s2 =''.join(A),''.join(B)
        return dfs(s1,s2)

127 ms

目录

0854：相似度为 K 的字符串（2377 分）

题目

分析

解答