用 Python 编写程序，查找 K 相似字符串的 K 的最小值

pythonserver side programmingprogramming更新于 2025/12/13 21:32:17

假设我们有两个字符串 s 和 t。如果我们可以将 s 中两个字母的位置交换 K 次，使结果字符串为 t，则这两个字符串是 K 相似的。因此，我们有两个字母重排词 s 和 t，我们必须找到使 s 和 t 是 K 相似的最小 K。

因此，如果输入为 s = "abc" t = "bac"，则输出为 1。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 neighbours() 。这将获取 new_data
对于 new_data 中的每个索引 i 和值 c，执行
- 如果 c 与 t[i] 不同，则
  - 退出循环
对于 j，范围为 i+1 到 new_data 的大小 - 1，执行
- 如果 u[j] 与 t[i] 相同，则
  - 交换 new_data[i] new_data[j]
  - 通过连接 new_data 中的所有元素生成一个字符串并返回，从下一次调用开始，从此区域重新开始
  - 交换 new_data[i] new_data[j]
从主方法中，执行以下操作:
q := 创建一个队列并插入对 (s, 0)
seen := 来自 s 的新集合
当 q 不为空时，执行
- (u, swap_cnt) := q 的第一项并将其从 q 中删除
- 如果 u 与 t 相同，则
  - 返回 swap_cnt
- 对于邻居中的每个 v(u 作为列表)，执行
  - 如果 v 不在 seen 中，则
    - 将 v 标记为已看到
    - 在 q 末尾插入 (v, swap_cnt+1)
返回 0

示例

让我们看看下面的实现以便更好地理解

from collections import deque
def solve(s, t):
   def swap(data, i, j):
      data[i], data[j] = data[j], data[i]

   def neighbors(new_data):
      for i, c in enumerate(new_data):
         if c != t[i]: break

      for j in range(i+1, len(new_data)):
         if u[j] == t[i]:
            swap(new_data, i, j)
            yield "".join(new_data)
            swap(new_data, i, j)

   q = deque([(s, 0)])
   seen = set(s)
   while q:
      u, swap_cnt = q.popleft()
      if u == t:
         return swap_cnt
      for v in neighbors(list(u)):
         if v not in seen:
            seen.add(v)
            q.append((v, swap_cnt+1))
   return 0

s = "abc"
t = "bac"
print(solve(s, t))