目录

LC 854. 相似度为 K 的字符串 (opens new window) (opens new window)

困难

# 问题描述

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

给你两个字母异位词 s1s2 ,返回 s1s2 的相似度 k 的最小值。

示例 1:

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

示例 2:

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

提示:

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

# 广度优先搜索

数据范围比较少,可以遍历字符串,查找枚举交换可能的情况,最终最早交换到目标字符串所需的部署即为相似度。由于交换之后可能存在与之前相同的情况,可以使用记忆化搜索方式减少重复的情况。

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var kSimilarity = function (s1, s2) {
  const n = s1.length
  const swap = (str, i, j) => {
    const arr = str.split('')
    const tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
    return arr.join('')
  }
  const visited = new Set()
  let queue = [[s1, 0]]
  let step = 0
  while (queue.length) {
    const q = []
    for (let i = 0; i < queue.length; i++) {
      let [curr, pos] = queue[i]
      if (curr === s2) return step
      while (pos < n && curr[pos] === s2[pos]) pos++
      for (let i = pos; i < n; i++) {
        if (curr[i] === s2[i]) continue
        if (curr[i] === s2[pos]) {
          const str = swap(curr, i, pos)
          if (!visited.has(str)) {
            visited.add(str)
            q.push([str, pos])
          }
        }
      }
    }
    queue = q
    step++
  }
  return step
}
上次更新: 2023/01/31 19:48:05

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 , 转载请注明出处!