【算法】实战题目

0315美团

小美的文本文件

小美有一个由大小写字母混合构成的加密字符串s，你需要按照以下准则将其解密得到字符串t。初始时字符串t为空，对于字符串s的每一个字符：
如果s的第i个字符为’R’（保证至多出现一次），则反转字符串t。
如果s的第i个字符为’Z’（保证至多出现一次），则撤销上一步操作，具体地：
如果上一步为‘R’，则取消反转；
如果上一步为其他字符，删除这个字符；
上一步为空，则跳过这个操作；
其他情况，直接将这个字符添加到字符串t的末尾。请你直接输出解密完成后的字符串t。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def decrypt_string(s: str) -> str:
    t = []                 # 用列表模拟字符串 t 的字符数组
    history = []           # 记录每一步操作，方便处理 'Z' 回滚
    for i, c in enumerate(s):
        if c == 'R':
            t.reverse()
            history.append('R')  # 记录反转操作
        elif c == 'Z':
            if history:
                last_op = history.pop()
                if last_op == 'R':
                    t.reverse()  # 撤销反转
                else:
                    if t:
                        t.pop()  # 撤销添加的字符
        else:
            t.append(c)
            history.append(c)     # 记录普通字符添加操作
    return ''.join(t)

# 读取多组输入
T = int(input())
for _ in range(T):
    s = input().strip()
    result = decrypt_string(s)
    print(result)