题目描述

对于某些非负整数 k，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2，则认为字符串 s1 和 s2 的 相似度为 k。

给你两个字母异位词 s1 和 s2，返回 s1 和 s2 的相似度 k 的最小值。

样例

输入：s1 = "ab", s2 = "ba"
输出：1

输入：s1 = "abc", s2 = "bca"
输出：2

提示

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

算法

(宽度优先搜索 / BFS)

1. 我们通过宽度有限搜索，从字符串 s1 开始扩展状态。我们把每一次交换算作一步，通过哈希表记录每个状态的最短步数。
2. 这里需要应用一个优化：在每次扩展中，找第一个当前字符串和 s2 不相等的位置 i，我们就针对这个 i 进行交换。我们往后找 j 满足当前字符串的第 j 的位置和 s2[i] 相等，对所有这样的 j 做扩展。

时间复杂度

• 由于状态扩展很复杂，只能大致确定时间复杂度不是多项式的，具体可以参考 LeetCode 给出的 题解 中时间复杂度的分析。

空间复杂度

• 时间复杂度 $t$ 乘上字符串长度 $N$。

C++ 代码

class Solution {
public:
    int kSimilarity(string s1, string s2) {
        const int n = s1.size();
        unordered_map<string, int> dis;

        dis[s1] = 0;
        queue<string> q;
        q.push(s1);

        while (!q.empty()) {
            string u(q.front());
            q.pop();

            if (u == s2)
                return dis[s2];

            string v(u);

            for (int i = 0; i < n; i++) {
                if (v[i] == s2[i])
                    continue;

                for (int j = i + 1; j < n; j++) {
                    if (v[j] != s2[i])
                        continue;

                    swap(v[i], v[j]);

                    if (dis.find(v) == dis.end()) {
                        dis[v] = dis[u] + 1;
                        q.push(v);
                    }

                    swap(v[i], v[j]);
                }

                break;
            }
        }

        return -1;
    }
};