0854. K-Similar Strings

题目信息

题号:

0854

难度:

Hard

主题:

字符串、字符交换、最少操作

原题:

LeetCode 0854

重点:

两个字符串保证互为字母异位词;一次操作可交换 s1 中任意两个位置,返回变成 s2 的最少交换次数

题目重述

给定长度相同的字符串 s1 和 s2,它们包含完全相同的字符及出现次数。一次操作可以选择 s1 中两个不同下标并交换这两个字符。

请返回把 s1 变成 s2 所需的最少交换次数。每次交换可以选择任意两个位置,不要求相邻;两个字符串原本相同时,最少交换次数为 0。

1 <= s1.length == s2.length <= 20,两个字符串只包含字符 a 至 f,并保证互为字母异位词。

自建示例

三个错位字符需要两次交换:

输入:s1 = "abca", s2 = "caba"
输出:2
解释:可以先交换下标 0 和 2,得到 "cbaa",再交换下标 1 和 2,得到 "caba";一次交换无法同时修正三个错位位置。

两个字符串已经相同:

输入:s1 = "face", s2 = "face"
输出:0
解释:不执行交换就已经得到目标字符串,因此最小 k 为 0。所有字符都位于题目允许的 a 至 f 范围内。