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

在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))

输入

"abc, bac"

输出

1

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程