在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]不同,则
- 退出循环
- 如果c与t [i]不同,则
- 对于j的范围i + 1到new_data的大小 – 1,执行以下操作
- 如果u [j]与t [i]相同,则
- 交换new_data [i] new_data [j]
- 如果u [j]与t [i]相同,则
通过连接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