在 Python 中为 K-Similar Strings 寻找 K 的最小值的程序
假设我们有两个字符串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))输入
"abc, bac"输出结果
1