LeetCode 854. 相似度为 K 的字符串

2021-07-20 HGNULB 约 11 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 854. 相似度为 K 的字符串

题意分析

给两个互为字母异位词的字符串 s1、s2，一次操作可以交换 s1 中任意两个位置的字符，问最少多少次操作能把 s1 变成 s2。

「任意两个位置」这个措辞很重要：不限于相邻交换，所以这不是逆序对计数，而是置换分解问题。也正因为交换是自由的，从一个字符串出发能一步到达的邻居非常多，直接搜索的分支因子会爆炸。

题目保证两串互为异位词，因此答案一定存在，不需要处理无解。同时保证 s1.length 最多 20，字符集只有 a 到 f 六种。串长 20 说明状态空间上界是 $20!$ 这个级别，暴力枚举排列绝无可能；但字符集只有 6 种又意味着重复字符很多，真正不同的状态数远小于阶乘，且有效的交换动作很有限——这两条约束合起来在提示：用搜索，但必须狠狠剪枝。

「最少操作次数」且「每次操作代价相同」，是无权图上求最短路的标准信号，广度优先搜索天然按代价分层，第一次抵达目标即最优。

边界：两串本来就相等时答案是 0；两串只有两个位置不同时答案是 1；最坏情况下答案不超过 n - 1。

解法：BFS + “首个不匹配位”剪枝

核心思路

把每个字符串看成图中的一个节点，一次交换是一条无权边，问题就是求 s1 到 s2 的最短路。BFS 按层扩展，第一次弹出 s2 时的层号就是答案。

朴素 BFS 的瓶颈立刻显现：一个长度 20 的串有 $\binom{20}{2} = 190$ 种交换方式，分支因子 190、深度可能到 19，状态数完全不可控。必须削减「每一步允许尝试的交换」。

第一个观察：已经匹配的位置不该动。如果 cur[i] == s2[i]，把它换走一定要再换回来，等于白白多花至少一次操作，绝不会出现在某条最短路径上。

第二个观察，也是本题的核心剪枝：可以只固定处理第一个不匹配位置。设 i 是最小的满足 cur[i] != s2[i] 的下标。这个位置迟早要被修正，而在最优解里，交换操作之间的先后顺序是可以任意重排的（每次操作影响两个位置，把「修 i」这一步提到最前面不会增加总步数）。所以我们不妨规定：当前这一步必须把位置 i 修好。这一条把分支因子从 $\binom{n}{2}$ 压到「有多少个 j 能供给正确字符」。

第三个观察：候选的 j 还要满足两个条件。cur[j] == s2[i] 保证这次交换真的把 i 修好；cur[j] != s2[j] 保证 j 本来就是错的——如果 j 位置本来是对的，换过去只是把错误从 i 挪到 j，白费一步。

不变量：BFS 第 k 层里的每个字符串，都恰好能用 k 次交换从 s1 得到，且不存在更短的交换序列把 s1 变成它。visited 保证每个字符串只被展开一次，因此第一次遇到 s2 时对应的层号就是最少交换次数。

状态用字符串本身表示、visited 用哈希集合去重，是这里最省事的选择：串长只有 20，哈希开销可以接受，也不需要设计编码。

解题步骤

先判 s1.equals(s2) 返回 0：这一步不只是快捷路径，也让后面的主循环可以假设起点不是终点，逻辑更干净。

初始化队列与访问集：队列放入 s1，visited 同时加入 s1，step = 0。入队即标记，而不是出队才标记——否则同一个字符串会被不同前驱重复入队，队列规模成倍膨胀。

分层 BFS：外层 while 每轮先取 size = queue.size()，内层恰好处理这么多个元素，处理完 step++。取 size 的快照是分层的关键，本轮新入队的元素属于下一层，不能混进来。

出队后先判终点：cur.equals(s2) 时返回 step。因为标记发生在入队时，节点入队时的层号与出队时的 step 一致，返回 step 而不是 step + 1。

定位第一个不匹配位 i：从左往右跳过所有 cur[i] == s2[i]。若扫到末尾说明整串已匹配，也返回 step（与上一条等价，是一层冗余保护）。

枚举 j 从 i + 1 开始：j 无需从 0 开始，因为 i 之前的位置全部已匹配，按第二条观察不该动。筛选条件 cur[j] == s2[i] && cur[j] != s2[j] 缺一不可：前者保证这一步有效，后者避免把已对位的字符换走。

交换生成新串并入队：visited.add(next) 返回 true 才入队，一行完成「去重 + 标记」。

以 s1 = "abac"、s2 = "baca" 走一遍。

两串不等，queue = ["abac"]，visited = {"abac"}，step = 0。

第 0 层：弹出 "abac"，不等于 s2。找首个不匹配位：下标 0 上 a 对 b，不匹配，i = 0，需要把 b 换到位置 0。枚举 j：j = 1 时 cur[1] = 'b' == s2[0] = 'b' 且 cur[1] = 'b' != s2[1] = 'a'，合格，交换后得 "baac"，入队；j = 2 时 cur[2] = 'a' != 'b'，跳过；j = 3 时 cur[3] = 'c' != 'b'，跳过。本层结束，step = 1。

第 1 层：弹出 "baac"，不等于 s2。首个不匹配位：下标 0 是 b 对 b 匹配，下标 1 是 a 对 a 匹配，下标 2 是 a 对 c，不匹配，i = 2，需要把 c 换到位置 2。枚举 j = 3：cur[3] = 'c' == s2[2] = 'c' 且 cur[3] = 'c' != s2[3] = 'a'，合格，交换后得 "baca"，入队。本层结束，step = 2。

第 2 层：弹出 "baca"，等于 s2，返回 step = 2。

对照一下没有剪枝会怎样：第 0 层就要生成 "abac" 的全部 6 种交换结果，其中 "aabc"、"acab" 之类根本无助于修正位置 0，它们还要继续展开各自的 6 个邻居。剪枝把第 0 层的分支从 6 个压到了 1 个。

代码实现

class Solution {
    public int kSimilarity(String s1, String s2) {
        if (s1.equals(s2)) {
            return 0;
        }

        ArrayDeque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(s1);
        visited.add(s1);

        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int t = 0; t < size; t++) {
                String cur = queue.poll();
                if (cur.equals(s2)) {
                    return step;
                }

                int i = 0;
                while (i < cur.length() && cur.charAt(i) == s2.charAt(i)) {
                    i++;
                }
                if (i == cur.length()) {
                    return step;
                }

                for (int j = i + 1; j < cur.length(); j++) {
                    if (cur.charAt(j) == s2.charAt(i) && cur.charAt(j) != s2.charAt(j)) {
                        String next = swap(cur, i, j);
                        if (visited.add(next)) {
                            queue.offer(next);
                        }
                    }
                }
            }
            step++;
        }
        return step;
    }

    private String swap(String s, int i, int j) {
        char[] a = s.toCharArray();
        char tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        return new String(a);
    }
}

func kSimilarity(s1 string, s2 string) int {
    if s1 == s2 {
        return 0
    }

    swap := func(s string, i, j int) string {
        a := []byte(s)
        a[i], a[j] = a[j], a[i]
        return string(a)
    }

    queue := []string{s1}
    visited := map[string]bool{s1: true}
    step := 0

    for len(queue) > 0 {
        size := len(queue)
        for t := 0; t < size; t++ {
            cur := queue[t]
            if cur == s2 {
                return step
            }

            i := 0
            for i < len(cur) && cur[i] == s2[i] {
                i++
            }
            if i == len(cur) {
                return step
            }

            for j := i + 1; j < len(cur); j++ {
                if cur[j] == s2[i] && cur[j] != s2[j] {
                    next := swap(cur, i, j)
                    if !visited[next] {
                        visited[next] = true
                        queue = append(queue, next)
                    }
                }
            }
        }
        queue = queue[size:]
        step++
    }
    return step
}

复杂度分析

时间复杂度：$O(S \cdot n^2)$，其中 $S$ 是剪枝后实际访问到的字符串状态数。每个状态要花 $O(n)$ 找首个不匹配位、$O(n)$ 枚举 j，每次交换还要 $O(n)$ 复制字符数组并做哈希。$S$ 的理论上界是 $n!$，但「只修首个不匹配位」把分支因子压到最多 5（字符集只有 6 种，能提供目标字符的错位 j 很少），实际远远达不到上界。

空间复杂度：$O(S \cdot n)$，队列与 visited 里各存若干长度为 $n$ 的字符串，两者同阶。这也是 BFS 相对 DFS 的固有代价——用空间换「首次抵达即最优」的保证。

关键点总结

「每步代价相同，求最少步数」几乎总是 BFS：按层扩展天然保证第一次抵达即最短，不需要像 DFS 那样搜完全部路径再取最小。

状态空间爆炸时，剪枝的正确姿势是证明「某类动作绝不出现在某条最优解里」，而不是凭感觉砍分支。本题两条剪枝都有严格理由：动已匹配位必然浪费、把修首个错位的操作提前不增加总步数。

固定「本步必须修好第一个不匹配位」是一种强有力的规范化技巧：它不减少可达的最优解，却把同一组交换的 $k!$ 种排列压成一种，搜索树瞬间瘦身。

访问标记要在入队时打，不是出队时打。出队才标记会让同一状态被多个前驱重复入队，队列膨胀且层号统计仍正确但性能崩坏。

分层 BFS 必须先取 size 快照再进内层循环，否则本层新入队的元素会被算进当前层，步数少算。

面试视角：先说「这是无权图最短路，用 BFS」拿到基本分，再主动指出「朴素 BFS 分支因子 $\binom{n}{2}$ 会超时」并给出首个不匹配位剪枝，是这题从及格到优秀的分界线。

易错点总结

出队时才加入 visited：s1 = "abac"、s2 = "baca" 这类有多条等长路径的输入，同一个中间串会被反复入队，队列规模指数增长，长串直接超时或内存溢出。

返回 step + 1：入队时已按层号计数，出队命中终点时返回 step + 1 会把答案统一多算 1，s1 = "ab"、s2 = "ba" 会返回 2 而不是 1。

忘记开头的 s1.equals(s2) 判断，且主循环里也不判终点：起点即终点时会一路搜索找不到新状态，最终返回一个大于 0 的 step，正确答案是 0。

j 从 0 开始枚举：i 之前的位置都已匹配，从 0 起会生成大量「把对的换错」的状态，"abcdef" 这类长串上状态数暴涨，超时。

筛选条件漏掉 cur[j] != s2[j]：cur = "ba"、s2 = "ab" 之外的场景中，会把本已就位的字符换走，多出一步，虽然仍能搜到答案但状态数成倍增加。

筛选条件漏掉 cur[j] == s2[i]：这一步的交换不再保证修好位置 i，「只修首个错位」的规范化前提被破坏，剪枝失效，退化成朴素 BFS。

不做分层、用 queue 里存 (串, 步数) 但忘记初始步数为 0：初始存 1 会让所有答案偏移 1，s1 == s2 之外的所有用例全错。

Go 版在内层循环里用 range queue：循环过程中 append 会改变切片，range 的行为是按初始长度迭代，看似正确但一旦有人改成 for i := range queue 就会把新入队元素当成本层，步数少算；显式取 size 快照更安全。

swap 里直接改原字符串的底层数组：Java 中若复用同一个 char[] 而不每次 toCharArray，前一次交换的结果会污染后续分支，"abac" 的多个 j 候选会互相干扰生成错误状态。

用 DFS 求最少交换次数而不剪枝到底：DFS 找到的第一条路径不保证最短，必须搜遍全部分支再取最小，在 n = 20 时不可能跑完。

相似题目

题目	难度	考察点
752. 打开转盘锁	中等	邻居由「拨动一位」固定生成，分支因子恒为 8，无需设计剪枝
127. 单词接龙	困难	邻居要在词表里查，重点是用通配符建桶把邻接查询降到 $O(L)$
433. 最小基因变化	中等	与 127 同构但字符集只有 4 种、串长固定 8，可直接枚举全部变异
773. 滑动谜题	困难	状态编码成字符串后 BFS，邻居由空格的可移动方向预先打表决定
815. 公交路线	困难	建图对象是「路线」而非「站点」，选错节点定义会让状态数爆炸
1345. 跳跃游戏 IV	困难	同值下标构成超级边，用完即清空该值的桶，否则重复展开导致 $O(n^2)$
909. 蛇梯棋	中等	难点在棋盘的蛇形编号与二维坐标互转，BFS 本身是模板
994. 腐烂的橘子	中等	多源 BFS，起点一次性全部入队，还要检查是否有永不腐烂的格子
765. 情侣牵手	困难	同为最少交换次数，但可用并查集按环长直接算出，无需搜索
LCR 108. 单词接龙	困难	与 127 同题
LCR 109. 打开转盘锁	中等	与 752 同题