โปรแกรมหาสตริงเล็กซิโคกราฟิกน้อยที่สุดหลังดำเนินการใน Python

ปัญหา

สตริง s ตัวเลข มีการดำเนินการ 2 แบบ: 1) บวก a ให้ตำแหน่งคี่ (0-indexed) โมด 10 2) หมุนขวา b ตำแหน่ง ทำซ้ำได้ หาสตริงเล็กซิโคกราฟิกน้อยที่สุด

ตัวอย่าง

s="5323", a=9, b=2 → 2050 (หมุน→บวก→บวก→หมุน→บวก)

ขั้นตอนการแก้ปัญหา

1. BFS บนสถานะสตริง: seen := set(), deq := deque([s])
2. بينما deq:
   • curr := deq.popleft(), เพิ่มใน seen
   • ad := add_(curr, a) (บวก a ตำแหน่งคี่)
   • ถ้า ad not in seen: push deq, add seen
   • ro := rotate_(curr, b) (หมุนขวา b)
   • ถ้า ro not in seen: push deq, add seen
3. คืน min(seen)

การนำไปใช้งาน (Python)

from collections import deque
def add_(s, a):
    res = ""
    for idx, ch in enumerate(s):
        if idx % 2 == 1:
            num = (int(ch) + a) % 10
            res += str(num)
        else:
            res += ch
    return res

def rotate_(s, b):
    idx = len(s) - b
    return s[idx:] + s[:idx]

def solve(s, a, b):
    seen = set()
    deq = deque([s])
    while deq:
        curr = deq.popleft()
        seen.add(curr)
        ad = add_(curr, a)
        if ad not in seen:
            deq.append(ad)
            seen.add(ad)
        ro = rotate_(curr, b)
        if ro not in seen:
            deq.append(ro)
            seen.add(ro)
    return min(seen)

s = "5323"
a = 9
b = 2
print(solve(s, a, b))

อินพุต

"5323", 9, 2

เอาต์พุต

2050