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"

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

1

更新于: 2021年10月8日

181 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告