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

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
字符串 哈希表 广度优先搜索

题目描述

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

image-20260929105015230

题意分析

s1 和 s2 互为字母异位词，每次可以交换 s1 的任意两个位置，求变成 s2 所需的最少次数。相同字符可能出现多次，选择哪一次出现参与交换，会影响后续需要多少步。

解法：广度优先搜索 + 首个错位剪枝

核心思路

[!blue]

把一个字符串看作一个状态，一次交换就是代价为 1 的状态转移。广度优先搜索按交换次数逐层展开，第一次取出目标串时，对应层号就是最少次数。但若每个状态枚举所有位置对，会产生大量无用交换，需要缩小候选范围。

找到当前串 cur 的首个错位 i，只枚举满足 j > i、cur[j] == s2[i]、cur[j] != s2[j] 的位置 j。交换后立刻修好 i，也不会破坏已经正确的前缀；最后一个条件还避免从已经匹配的位置借走字符。由于两串字母数量相同，首个错位需要的字符一定能在后方某个错位处找到。

为什么这种剪枝仍保留最优路径？可以把相同字符的每次出现暂时看作不同对象，为它们选择最终对应位置。这个对应会分解成若干置换环，长度为 t 的环需要 t - 1 次交换：每次至多把一个环拆成两个，而逐个固定位置也能达到这个次数。选择环数最多的对应关系，就得到最少交换数；其中已经匹配的位置可以各自独立成单点环。

首个错位 i 所在的环中，必有一个位置 j 持有要送到 i 的字符。交换这两个位置，能把 i 拆成单点环，使剩余最少交换数减少一。这个 j 自身仍错位，而 i 之前已经全部匹配，所以 j > i，恰好属于代码保留的候选。我们不需要实际求置换环，只需知道枚举中至少有一步能沿着最优路径前进。

可能有多个位置都能提供同一个字符，仍要全部尝试，不能随便选一个。每个候选都从当前串的独立副本交换，访问集合在入队时去重；固定每层原有的队列大小，新状态留到下一层，才能让层号准确等于交换次数。

解题步骤

  1. 起点入队并标记，初始交换次数为零。
  2. 固定当前层大小，逐个取出字符串。
  3. 若取出的字符串等于目标，返回当前层号；否则找到首个错位，枚举后方可提供正确字符的错位位置。
  4. 用独立副本生成交换结果，未访问过就标记并入队，供下一层处理。
  5. 当前层全部处理完后，交换次数加一。两串原本相同则直接返回 0。

代码实现

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(Sn^2)$，S 为实际访问状态数，n 为字符串长度；生成与哈希新字符串也需要线性成本。
  • 空间复杂度：$O(Sn)$，队列和访问集合保存字符串状态。

关键点总结

[!green]

  • 每层对应一次交换，先到目标得到最少次数。
  • 每步固定首个错位，保留已匹配前缀。
  • 相同目标字符可以来自多个位置，需要枚举而非随便选一个。
  • 剪枝的依据是至少保留一条最优路径，不是声称所有最优交换都必须先修正同一位置。

易错点总结

[!yellow]

  • 首个合格交换就直接作为最终选择：可能错过更少总交换的分支。
  • 不区分当前层和新入队状态：交换次数统计错误。
  • 生成下一分支时沿用前一次交换而不恢复：候选不再从同一状态出发。
  • 把任意交换当作只能相邻交换：求成了另一种距离。

相似题目

题目 难度 关联与区别
补充题 101. 数组排序的最少交换次数 困难 元素唯一时可直接按置换环计交换数，本题重复字符的目标位置对应关系不唯一，不能随意固定匹配。
839. 相似字符串组 困难 原题判断一次交换是否相似并分组，本题求把两串变成相同所需的最少交换数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/60630718
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！