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

Categories:

题目描述
思路分析
1. 解法一：广度优先搜索（推荐）
相似题目

题目描述

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

思路分析

解法一：广度优先搜索（推荐）

核心思路：

将每个字符串视为图中的一个节点，两个字符串”相邻”当且仅当可以通过一次相邻字符交换从一个得到另一个

从字符串 s1 出发进行 BFS，找到第一个到达 s2 的最短路径长度即为答案

每一层 BFS 对应一次交换操作，找到第一个不匹配位置 i，然后枚举 j > i 使得 s[j] == s1[i]，交换后得到新状态

使用哈希集合记录已访问状态，避免重复搜索

复杂度分析：

时间复杂度：O(n² · n! · n)，其中 n 为字符串长度，最坏情况下需要搜索所有排列

空间复杂度：O(n · n!)，存储所有可能的字符串状态

class Solution {
  public int kSimilarity(String s1, String s2) {
    // 若两字符串相同，无需交换
    if (s1.equals(s2)) {
      return 0;
    }

    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.offer(s1);
    visited.add(s1);
    int step = 0;

    while (!queue.isEmpty()) {
      step++;
      int size = queue.size();

      // 逐层处理
      for (int i = 0; i < size; i++) {
        String cur = queue.poll();

        // 找到第一个与 s2 不匹配的位置
        int j = 0;
        while (cur.charAt(j) == s2.charAt(j)) {
          j++;
        }

        // 枚举可交换的位置
        for (int k = j + 1; k < cur.length(); k++) {
          if (cur.charAt(k) == s2.charAt(j) && cur.charAt(k) != s2.charAt(k)) {
            String next = swap(cur, j, k);
            if (next.equals(s2)) {
              return step;
            }
            if (visited.add(next)) {
              queue.offer(next);
            }
          }
        }
      }
    }

    return step;
  }

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

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

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

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

    for len(queue) > 0 {
        step++
        size := len(queue)

        // 逐层处理
        for i := 0; i < size; i++ {
            cur := queue[i]

            // 找到第一个与 s2 不匹配的位置
            j := 0
            for cur[j] == s2[j] {
                j++
            }

            // 枚举可交换的位置
            for k := j + 1; k < len(cur); k++ {
                if cur[k] == s2[j] && cur[k] != s2[k] {
                    next := swap(cur, j, k)
                    if next == s2 {
                        return step
                    }
                    if !visited[next] {
                        visited[next] = true
                        queue = append(queue, next)
                    }
                }
            }
        }

        queue = queue[size:]
    }

    return step
}

相似题目

题目	难度	考察点
765. 情侣牵手	困难	贪心、BFS
126. 单词接龙 II	困难	广度优先搜索
127. 单词接龙	困难	广度优先搜索
433. 最小基因变化	中等	广度优先搜索
567. 字符串的排列	中等	滑动窗口
1722. 执行交换操作后的最小汉明距离	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/60630718