1225. 正则问题
摘要
Title: 1225. 正则问题
Tag: 二叉树、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1225. 正则问题
-
题意
考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。 -
思路
-
代码
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
27
28
29
30'''
Author: NEFU AB-IN
Date: 2022-04-01 20:38:53
FilePath: \ACM\Acwing\1225.py
LastEditTime: 2022-04-01 20:38:54
'''
k = 0
def dfs():
global k
res = 0
while k < len(a):
if a[k] == '(':
k += 1 #跳过左括号
res += dfs() #计算括号内的
k += 1 #跳过右括号
elif a[k] == '|':
k += 1 #跳过或运算符
res = max(res, dfs()) #和右边的取最大值
elif a[k] == ')': #遇到右括号就结束此层dfs
break
else:
res += 1 #加上每个x
k += 1 #跳过’x'
return res
a = input().strip()
print(dfs())
