数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找K相似字符串的最小K值
假设我们有两个字符串s和t。如果我们可以精确交换s中两个字母的位置K次，使得结果字符串为t，则这两个字符串是K相似的。因此，我们有两个异位词s和t，我们需要找到s和t为K相似的最小K值。
所以，如果输入类似于s = "abc" t = "bac"，则输出将为1。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数neighbors()。这将接收new_data作为输入。
对于new_data中的每个索引i和值c，执行以下操作：
如果c与t[i]不同，则
退出循环。
对于从i+1到new_data大小-1的范围内的每个j，执行以下操作：
如果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。
对于neighbors(u作为列表)中的每个v，执行以下操作：
如果v不在seen中，则
标记v为已访问。
将(v, swap_cnt+1)插入到q的末尾。
返回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
更新于: 2021年10月8日
181 次浏览
广告