AcWing 1225. 正则问题
原题链接
中等
作者:
季之秋
,
2021-03-26 16:34:41
,
所有人可见
,
阅读 178
/*
遇到括号和|就递归到下一层,直到遇见右括号 || 出界, 括号是答案加上里面的值,
| 是这一层原来的答案和新的一层答案取最大值 , 遇到右括号就break到对应的左括号,
每种情况都需要使k++ ,以右括号做递归结束条件
*/
import java.util.*;
public class Main{
static String s;
static int k=0;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
s=sc.next();
System.out.println(dfs());
}
static int dfs(){ //当前的情况
int res=0; // 当前情况的答案
while(k<s.length()){ //防出界 , 分遇到的四种符号处理
if(s.charAt(k) == '('){ // 即使多个括号也可以递归括号
k++; //跳过 ‘(’
res += dfs(); // 加上括号内的答案
k++; // 跳过 ')'
}else if(s.charAt(k) == ')') break; // 可以一直break到原来的左括号
else if(s.charAt(k) == '|'){ //当前情况是没有遇到括号,所以在一个括号里
// 左边的答案是res,右边是递归到break 的 ‘)’为止
k++;
res=Math.max(res, dfs());
}
else{
res++;
k++;
}
}
return res;
}
}