Chương trình kiểm tra có thể chuyển đổi chuỗi trong K bước không bằng Python

Cho chuỗi s, t. Kiểm tra s có thể biến thành t trong ≤ k bước. Bước i: chọn index j chưa chọn, shift ký tự tại j lên i lần (z→a). Có thể bỏ qua bước.

Ví dụ: s="poput", t="vwput", k=9 → True (bước 6: p→v, bước 8: o→w).

Thuật toán

• Nếu len(s) != len(t): return False
• count[i] = min(1, k-i+1) + (k-i)//26 cho i=0..25 (số lần có thể shift i)
• Duyệt cặp ký tự (c1, c2):
  • Nếu c1!=c2: diff = (ord(c2)-ord(c1)+26)%26
  • Nếu count[diff] <= 0: return False
  • count[diff] -= 1
• Return True

Code Python

def solve(s, t, k):
    if len(s) != len(t):
        return False
    count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)]
    for c1, c2 in zip(s, t):
        if c1 != c2:
            diff = (ord(c2) - ord(c1) + 26) % 26
            if count[diff] <= 0:
                return False
            count[diff] -= 1
    return True

s = "poput"
t = "vwput"
k = 9
print(solve(s, t, k))

Input

"poput","vwput",9

Output

True