在Python中寻找K相似字符串的最小K值程序

假设我们有两个字符串s和t。如果我们可以在s中交换两个字母的位置，恰好K次，使得结果字符串是t，那么这两个字符串就是K相似的。因此，如果有两个变位词s和t，我们必须找到最小的K值，使得s和t是K相似的。

因此，如果输入是s =“abc”t =“bac”，那么输出将是1。

为了解决这个问题，我们将采取以下步骤确定。

定义一个函数neighbors()。这将采用new_data
对于每个指数i和值c在new_data中，执行以下操作
- 如果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创建一个新集合
while q不为空，执行以下操作：
- （u，swap_cnt）：=q的第一个项目并从q中删除它
- 如果u与t相同，则
  - 返回swap_cnt
- 对于邻居中的每个v，执行以下操作
  - 如果v不在已看到，则
  - 将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))