Python - Trạng thái cuối cùng của chuỗi sau khi biến đổi

Giả sử chúng ta có chuỗi S độ dài n. Có n hộp liền kề, ký tự R tại vị trí i nghĩa là hộp thứ i bị đẩy sang phải. Tương tự L tại vị trí i nghĩa là đẩy sang trái, dấu '.' chỉ ô trống. Từ cấu hình ban đầu, tại mỗi đơn vị thời gian, hộp bị đẩy sang phải có thể đẩy hộp tiếp theo sang phải, tương tự cho trái. Chúng ta phải tìm vị trí cuối cùng của tất cả hộp khi không còn di chuyển khả thi.

Ví dụ, nếu đầu vào là "R..R...L.", thì đầu ra là "RRRRR.LL.".

Giải pháp:

• N = len(string), movement = [0]*N, m=0
• Duyệt trái sang phải: nếu 'R' -> m=N; nếu 'L' -> m=0; else m=max(m-1,0); movement[i] += m
• m=0; duyệt phải sang trái: nếu 'L' -> m=N; nếu 'R' -> m=0; else m=max(m-1,0); movement[i] -= m
• Kết quả: join '.' nếu m==0 else 'R' nếu m>0 else 'L' cho mỗi m trong movement.

Ví dụ Code

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.'))

Đầu vào

'R..R...L.'

Đầu ra

RRRRR.LL.