题目要求: 现在给出一串字符串,字符串由 a ( ) | 组成,想要通过简单的规则得到字符串最后能够求出的最长字符串是多少? 例如 ((aa|aaa)a|(a|aa))aa 能接受的最长字符串是: aaaaaa,长度是6。 提示:|在这里是或的意思,选择字符多的那一边。 输入 一串字符串,字符串由 a ( ) | 组成 输出 一个数字,表示a的长度 样例输入 Copy ((aa|aaa)a|(a|aa))aa 样例输出 Copy 6
解题思路: 得学会总结一下题型了。本题不难,用递归是最好的方法。我自己没写出来,看了大佬的代码深感巧妙。 思路:递归函数用来处理一个()号内的字符串,返回其中最大数量的字符串数量,若遇到重复的括号,则开始递归,递归时会将小一级的括号内得到的值返回大一级的括号进行计算,直到最后只剩下一个括号。 总结:类似的需要重复操作并且不影响前面结果的问题,可以用递归解决。
通关代码:
#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;
}