相似度为 K 的字符串

题解方法

• 广度优先搜索

广度优先搜索

• 两字符串为字母异位词，保证必存在交换方案

• 给定的字符串的长度范围为 [1,20]，且只包含 6 种不同的字符，可以枚举所有可能的交换方案

• 搜索时通过剪枝提高效率

核心代码

广度优先搜索

Queue<Pair<String, Integer>> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();

queue.offer(new Pair<>(s1, 0));
visited.add(s1);

while (!queue.isEmpty()) {
    Pair<String, Integer> pair = queue.poll();
    String cur = pair.getKey();
    int step = pair.getValue();

    if (cur.equals(s2)) {
        return step;
    }

    int idx = 0;
    // 剪枝，找到第一个不同的字符
    while (cur.charAt(idx) == s2.charAt(idx)) {
        idx++;
    }

    for (int i = idx + 1; i < len; i++) {
        // 剪枝，找到第一个不同的字符
        if (cur.charAt(i) == s2.charAt(i)) {
            continue;
        }
        // 找到与 s2[idx] 相同的字符，交换
        if (cur.charAt(i) == s2.charAt(idx)) {
            String next = swap(cur, idx, i);
            if (!visited.contains(next)) {
                queue.offer(new Pair<>(next, step + 1));
                visited.add(next);
            }
        }
    }
}

题目来源

854. 相似度为 K 的字符串 - 力扣（LeetCode）