โปรแกรมตรวจสอบว่าแปลง String ได้ใน K Moves หรือไม่ด้วย Python

Move ที่ i: เลือก index j (1-based) ที่ยังไม่เลือก เปลี่ยนตัวอักษรที่ j โดย shift i ครั้ง (a->b->...->z->a) ตรวจสอบว่า s -> t ได้ใน ≤ k moves ใช้ frequency count ของ shift distances ที่จำเป็น ตรวจสอบว่าแต่ละ shift distance มี moves พอหรือไม่

อัลกอริทึม

1. ถ้า len(s) != len(t): return False
2. count[d] = จำนวน move ที่สามารถทำ shift distance d ได้ = min(1, k-d+1) + (k-d)//26 สำหรับ d=0..25
3. วนลูป c1, c2 ใน zip(s,t): ถ้า c1 != c2 คำนวณ diff = (ord(c2)-ord(c1)+26)%26
4. ถ้า count[diff] <= 0: return False
5. count[diff]--
6. คืน True

ตัวอย่างโค้ด

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))  # Output: True

อินพุต/เอาต์พุต

Input: "poput", "vwput", 9
Output: True

i=6: 'p' shift 6 -> 'v', i=8: 'o' shift 8 -> 'w'