模拟 + 双链表
看了视频讲解才做了出来
根据视频讲解的思路写的Python3版代码
注释很详细
def check(p): # 检查位置 p 上的字符是否为边缘字符,是的话将该位置添加到边缘字符位置的集合中
if s[l[p]] != '#' and s[r[p]] != '#':
if s[l[p]] != s[p] and s[p] == s[r[p]]:
edge.extend([p, l[p]])
if s[l[p]] == s[p] and s[p] != s[r[p]]:
edge.extend([p, r[p]])
s = ['#'] + list(input()) + ['#'] # 前后添加两个哨兵节点
n = len(s) - 2 # 字符串的长度
l, r = [0] + list(range(n)) + [0], [0] + list(range(2, n + 2)) + [0] # l[i]表示:i的前一个位置,r[i]同理
edge, is_edge = [], [False] * (n + 2) # 边缘字符的位置 该位置上的字符是否为已处理过的边缘字符
for i in range(1, n + 1): # 初次查找字符串中的边缘字符
check(i)
i = 0
while i < len(edge): # 遍历边缘字符的位置
latent = [] # 潜在的可能成为边缘字符的字符位置
while i < len(edge):
j = edge[i] # 边缘字符的位置
if not is_edge[j]: # 未处理过的边缘字符
l[r[j]], r[l[j]] = l[j], r[j] # 伪删除该字符
latent += [l[j], r[j]] # 与它相邻的两个字符视作潜在的字符
is_edge[j] = True # 标记为已处理
i += 1
for j in latent: # 遍历潜在的字符的位置
if not is_edge[j]: # 它没被删过
check(j) # 检查
ans = [s[i] for i in range(1, n + 1) if not is_edge[i]] # 答案
print("EMPTY" if len(ans) == 0 else ''.join(ans))
复杂度分析
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
Orz终于找到一个python题解了,辛苦啦~