算法 递归 回溯 搜索树

题意是在规则之下的xxxxx…的最大长度

• 规则1：() 的意思是有括号的先算括号里面的，优先级最高，把括号计算的结果在和括号外的字符拼接，即括号是相对独立，完整的个体

• 规则2：|的意思是|这个符号两侧的字符串只能选其中一个，由于这题要求能拼接的字符串最长，因此应该选择字符|字符串xxx...长度较大的一侧

如果递归的问题想不清楚的话，就画一颗递归搜索树 –yxc

比如样例中的字符串((xx|xxx)x|(x|xx))xx对应的递归搜索树如下

时间复杂度 $O(N)$

每个字符只会进栈一次，出栈一次，因此是线性的时间复杂度

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std ;

int k ;
string str ;

int dfs(){
    int res = 0 ;
    while(k<str.size()){
        if(str[k] == '('){
            k ++ ;
            res += dfs() ;
            k ++ ;
        }else if(str[k] == ')'){
            // k ++ ;
            break ;
        }else if(str[k] == '|'){
            k ++ ;
            res = max(res,dfs()) ;
        }else{
            k ++ ;
            res ++ ;
        }
    }
    return res ;
}

int main(){
    cin >> str ;

    cout << dfs() << endl ;

    return 0 ;

}