在 Python 中为 K-Similar Strings 寻找 K 的最小值的程序

Z时代
2024-01-10
分类：综合

假设我们有两个字符串 s 和 t。如果我们可以将 s 中两个字母的位置恰好交换 K 次，使得结果字符串是 t，则这两个字符串是 K 相似的。所以，我们有两个字谜 s 和 t，我们必须找到最小的 K，其中 s 和 t 是 K 相似的。

因此，如果输入类似于 s = "abc" t = "bac"，那么输出将为 1。

示例

让我们看下面的实现来更好地理解

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