LC 854. 相似度为 K 的字符串 (opens new window) (opens new window)
困难
# 问题描述
对于某些非负整数 k
,如果交换 s1
中两个字母的位置恰好 k
次,能够使结果字符串等于 s2
,则认为字符串 s1
和 s2
的 相似度为 k
。
给你两个字母异位词 s1
和 s2
,返回 s1
和 s2
的相似度 k
的最小值。
示例 1:
输入:s1 = "ab", s2 = "ba"
输出:1
示例 2:
输入:s1 = "abc", s2 = "bca"
输出:2
提示:
1 <= s1.length <= 20
s2.length == s1.length
s1
和s2
只包含集合{'a', 'b', 'c', 'd', 'e', 'f'}
中的小写字母s2
是s1
的一个字母异位词
# 广度优先搜索
数据范围比较少,可以遍历字符串,查找枚举交换可能的情况,最终最早交换到目标字符串所需的部署即为相似度。由于交换之后可能存在与之前相同的情况,可以使用记忆化搜索方式减少重复的情况。
/**
* @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 协议 , 转载请注明出处!