2020字节跳动：万万没想到之聪明的编辑[python][队列][正则][自动机]

解法一：队列+枚举

def repair(s):
    # AABB -> AAB | AAA -> A
    queue, res = [], []
    for i in s:
        queue.append(i)
        if len(queue)==4:
            if queue[0]==queue[1]==queue[2]:
                queue.pop(2)
            elif queue[1]==queue[2]==queue[3]:
                queue.pop(-1)
            elif queue[0]==queue[1] and queue[2]==queue[3]:
                queue.pop(-1)
            else:
                res.append(queue.pop(0))
    res += queue
    return ''.join(res)

# --- IO ---#
N = int(input())
for _i in range(N):
    print(repair(input())) # Notice: input() only for python3

解法二：正则

import re
def repair(s):
    # (.)\1 -> \1表示.匹配到的第一个字符
    res = re.sub(r'(.)\1\1+', repl=lambda x: x.groups(0)[0]*2, string=s) # 消除三个以上连续
    res = re.sub(r'(.)\1(.)\2', repl=lambda x: x.groups(0)[0]*2+x.groups(0)[1], string=res)
    return res

解法三：有限状态自动机

def repair(s):
    # 自动机 [X]表示循环条件
    #    [not A]   [A]   [B]
    #      |        |     |
    # -A-> S0 -A-> S1 -B> S2
    #  ^                  |
    #  |------not B-------|
    state, A, B = None, None, None
    res = []
    for i in s:
        res.append(i)
        if A is None:
            A, state = i, 0 # 提升状态并记录A
        elif state == 0:
            if i == A:
                state = 1 # 提升状态
            else:
                A = i # 状态不变A改变
        elif state == 1:
            if i == A:
                res.pop(-1) # 忽略这个A
            elif B is None:
                state, B = 2, i # 提升状态并记录B
        elif state == 2:
            if i == B:
                res.pop(-1) # 忽略这个B
            else:
                state, A, B = 0, i, None # 回退状态并更新A、B
    return ''.join(res)