迷失的括号序列题解

首先我们需要知道如何去判断一个括号序列是否合法，我们需要括号序列的任何一个前缀中左括号的个数大于等于右括号的个数，并且右括号总个数等于左括号总个数。首先我们要判断 $n$ 是否为偶数，因为奇数左括号右括号个数肯定就不相等了。总长度是 $n$ ，所以左括号个数应为 $n/2$ ，当然如果当前括号序列里面的左括号个数大于 $n/2$ ，那么也是不行的。接下来我们就可以计算出还需要补 $cnt$ 个左括号。为了尽可能满足前缀中左括号个数大于等于右括号个数，那么这 $cnt$ 个左括号肯定是替换最左边的 $cnt$ 个 $?$ ，因为左括号越早出现在左边对于我们来说是越优的，越不可能出现右括号个数比左括号个数多。最后再判断一下是不是合法的括号序列就OK啦。时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

class Solution {
public:
    string MissingBrackets(string brackets) {
        // write code here
        int cnt=0;
        for(int i=0;i<brackets.size();i++) 
            if(brackets[i]=='(') cnt++;
        if(cnt*2>brackets.size()||brackets.size()%2==1) 
            return "Impossible";
        int lef=brackets.size()/2-cnt;
        for(int i=0;i<brackets.size();i++) {
            if(brackets[i]=='?'&&lef) brackets[i]='(',lef--;
            else if(brackets[i]=='?') brackets[i]=')';
        }
        int all=0;
        for(int i=0;i<brackets.size();i++) {
            if(brackets[i]=='(') all++;
            else if(brackets[i]==')') all--;
            if(all<0) return "Impossible";
        }
        return brackets;
    }
};