图解LeetCode——854. 相似度为 K 的字符串（难度：困难）

源码 · 2024-9-26 04:42:59

一、标题

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，可以或许使效果字符串即是 s2 ，则以为字符串 s1 和 s2 的相似度为 k 。
给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
二、示例

2.1> 示例 1：

【输入】s1 = "ab", s2 = "ba"
【输出】1

2.2> 示例 2：

【输入】s1 = "abc", s2 = "bca"
【输出】2

提示：

1 <= s1.length <= 20
s2.length == s1.length
s1 和 s2 只包罗聚集 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母
s2 是 s1 的一个字母异位词

三、解题思绪

根据标题形貌，必要探求最小相似度，那么这道题我们可以接纳回溯算法来进行盘算。每次交换都会开辟一条新的“遍历路线”，那么每当我们走完一条路线之后，就必要通过回溯来走其他路线，终极根据盘算每条路线的交换次数，返回最小值即可。下面我们以s1=“bccaba”，s2=“abacba”为例，展示一条路线的交换遍历过程，如下图所示：

通过上面的图例，我们相识到了一条路线的盘算交换方式，但是，由于我们会针对每一步都会实验回溯使用（如果满足回溯条件的话），那么就会有N条路线。照旧以上面的例子，如下列出了大概
路线很多，但是我们也没有须要全都实验完每条路线的遍历使用。好比，当我们遍历一条路线进行交换使用的时间，发现已经高出了其他路线的最小交换次数，那么这条路线我们就没有须要在继承走下去了。详细的逻辑处置惩罚，请参照如下的代码实现。
四、代码实现

图解LeetCode——854. 相似度为 K 的字符串（难度：困难）

所属分类: 问答交流

新帖推荐: 30日

推荐作品