สถานะสุดท้ายของสตริงหลังปรับเปลี่ยนใน Python

สมมติว่าเรามีสตริง S ความยาวคือ n กล่อง n ช่องติดกัน ตัวอักษร R ที่ตำแหน่ง i แทนว่ากล่องที่ i ถูกผลักไปทางขวา ตัวอักษร L ที่ตำแหน่ง i แทนว่ากล่องที่ i ถูกผลักไปทางซ้าย จุด '.' แทนพื้นที่ว่าง เริ่มจากการตั้งค่าเริ่มต้น ที่ทุกหน่วยเวลา กล่องที่ถูกผลักไปขวาสามารถผลักกล่องถัดไปไปขวาได้ การกระทำเดียวกันใช้ได้กับด้านซ้าย เราต้องหาตำแหน่งสุดท้ายของกล่องทั้งหมดเมื่อไม่มีการเคลื่อนไหวที่เป็นไปได้อีก

ตัวอย่าง

หากอินพุตคือ R..R...L. ผลลัพธ์จะเป็น RRRRR.LL.

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

1. N := ความยาวของสตริง
2. movement := อาร์เรย์ขนาด N เติมด้วย 0
3. m := 0
4. ลูป i จาก 0 ถึง N:
   • ถ้า string[i] == 'R' ให้ m := N
   • อื่นๆ ถ้า string[i] == 'L' ให้ m := 0
   • อื่นๆ ให้ m := max(m - 1, 0)
   • movement[i] := movement[i] + m
5. m := 0
6. ลูป i จาก N - 1 ถึง -1 ลดทีละ 1:
   • ถ้า string[i] == 'L' ให้ m := N
   • อื่นๆ ถ้า string[i] == 'R' ให้ m := 0
   • อื่นๆ ให้ m := max(m - 1, 0)
   • movement[i] := movement[i] - m
7. คืนค่าสตริงโดยเพิ่มจุดถ้า m == 0 ไม่เช่นนั้น 'R' เมื่อ m > 0 ไม่เช่นนั้น 'L' สำหรับทุกองค์ประกอบ m ใน movement

การใช้งาน

def get_final_pos(string):
    N = len(string)
    movement = [0] * N
    m = 0
    for i in range(0, N):
        if string[i] == 'R':
            m = N
        elif string[i] == 'L':
            m = 0
        else:
            m = max(m - 1, 0)
        movement[i] += m
    m = 0
    for i in range(N - 1, -1, -1):
        if string[i] == 'L':
            m = N
        elif string[i] == 'R':
            m = 0
        else:
            m = max(m - 1, 0)
        movement[i] -= m
    return "".join('.' if m == 0 else 'R' if m > 0 else 'L' for m in movement)

print(get_final_pos('R..R...L.'))

อินพุต

'R..R...L.'

เอาต์พุต

RRRRR.LL.