前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >OJ刷题记录:问题 B: 简单正则

OJ刷题记录:问题 B: 简单正则

作者头像
英雄爱吃土豆片
发布2020-10-29 10:53:41
4040
发布2020-10-29 10:53:41
举报
文章被收录于专栏:英雄爱吃土豆片

问题 B: 简单正则

题目要求: 现在给出一串字符串,字符串由 a ( ) | 组成,想要通过简单的规则得到字符串最后能够求出的最长字符串是多少? 例如 ((aa|aaa)a|(a|aa))aa 能接受的最长字符串是: aaaaaa,长度是6。 提示:|在这里是或的意思,选择字符多的那一边。 输入 一串字符串,字符串由 a ( ) | 组成 输出 一个数字,表示a的长度 样例输入 Copy ((aa|aaa)a|(a|aa))aa 样例输出 Copy 6

解题思路: 得学会总结一下题型了。本题不难,用递归是最好的方法。我自己没写出来,看了大佬的代码深感巧妙。 思路:递归函数用来处理一个()号内的字符串,返回其中最大数量的字符串数量,若遇到重复的括号,则开始递归,递归时会将小一级的括号内得到的值返回大一级的括号进行计算,直到最后只剩下一个括号。 总结:类似的需要重复操作并且不影响前面结果的问题,可以用递归解决。

通关代码:

代码语言:javascript
复制
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string str;
int LEN, pos;

int fun() {
	int son = 0, res = 0;
	
	while (pos < LEN) {
		if (str[pos] == '(') {
			pos++;
			son += fun();
		} else if (str[pos] == '|') {
			pos++;
			res = max(son, res);
			son = 0;
		} else if (str[pos] == ')') {
			pos++;
			break;
		} else {
			pos++;
			son++;
		}
	}
	res = max(son, res);
	
	return res;
}

int main() {
	cin >> str;
	
	LEN = str.size();
	pos = 0;
	
	cout << fun();
	
	return 0;
} 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/08/28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题 B: 简单正则
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档