题解 | #迷失的括号序列#

思路：

题目的主要信息：

一个序列中仅有"("、")"、"?"三种符号，将其中的"?"替换成任意括号，使之变成一个括号合法的序列
括号合法的序列定义：
1. 空序列一定合法
2. (+合法括号序列+) 为合法括号序列
3. ()+合法括号序列为合法括号序列

通俗来说就是，一个左括号就一定有一个右括号匹配，同理一个右括号就一定有一个左括号匹配

如果能构造出来则返回恢复后任意合法的括号序列，否则返回Impossible

方法一：数组记录法
具体做法：
首先我们准备两个辅助数组，index记录问号"?"出现的下标，dp记录两个问号之间括号的差值，正数表示差相应右括号，负数表示差相应绝对值的左括号。
我们第一次对字符串进行遍历，将信息记录在两个辅助数组中。
然后，我们对每个问号"?"所在的位置进行判断，如果之前出现的左括号个数加上之前出现的问号数都小于右括号，则无法匹配成功，返回Impossible，否则我们可能匹配成功。
最后对问号进行替换，如果左括号多，即记录数大于0，则从右往左，先替换为右括号，再依次右括号、左括号得替换；如果右括号多即记录数小于0，则同理对称操作。

class Solution {
public:
    string MissingBrackets(string brackets) {
        int n = brackets.length();
        if(n % 2) //不为偶数一定不合法
            return "Impossible";
        vector<int> index;//index记录？出现的位置
        vector<int> dp; //y记录两个？之间左右括号个数的差
        int a = 0; //维护两个？之间左右括号个数的差
        for(int i = 0; i < n; i++){//找到？的位置，即之间的括号差
            if(brackets[i] == '?'){
                index.push_back(i);  //位置入数组
                dp.push_back(a);
                a = 0;
            }
            else if(brackets[i] == ')') //遇到左加，遇到右减
                a--;
            else
                a++;
        }
        index.push_back(n);
        dp.push_back(a);
        n = index.size(); 
        a = 0;
        int q = 0; //记录问号出现次数
        for(int i = 0; i < n; i++){
            a += dp[i];//相差求和
            if(-a > q++) //如果前面一直少，且少得还大于?出现的次数
                return "Impossible";
        }
        if(-a > index.size() - 1)   //把所有？变为左括号都不能使左括号数量大于右括号
            return "Impossible";
        if(a > 0){ //左括号较多
            a++;
            for(int i = n - 2; i >= 0; i--){
                if(a > 0){
                    brackets[index[i]] = ')';
                    a--;
                }
                else{
                    brackets[index[i]] = '(';
                    a++;
                }
            }
        }
        else{ //右括号较多
            a--;
            for(int i = 0; i < n - 1; i++){
                if(a < 0){
                    a++;
                    brackets[index[i]] = '(';
                }
                else{
                    brackets[index[i]] = ')';
                    a--;
                }
            }
        }
        return brackets;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，单独遍历两次
空间复杂度： $O(n)$ ，两个辅助数组长度都为 $n$

方法二：贪心
具体做法：
我们都直到合法的括号序列，左括号数与右括号数一定是各占一半。那么我们可以从括号数入手，每次都贪心地将差的左括号或者右括号补齐，最后再验证整个序列是否合法。
首先我们统计整个字符串中国左括号的数量，如果左括号数大于字符串长度的一半或者字符串长度不为偶数，我们可以断言这不可能组成合法序列。
再然后我们知道了左括号数是序列长度的一半，因此我们用 $n / 2 - count$ 得到还差多少左括号，然后我们遍历整个字符串，遇到一个问号我们查看是否还差左括号，如果差则将问号变成左括号，如果不差则将问号变成右括号。
图片说明
最后我们遍历字符串检查是否合法。

class Solution {
public:
    string MissingBrackets(string brackets) {
        int n = brackets.length();
        int count = 0; 
        for(int i = 0; i < n; i++) //统计左括号数
            if(brackets[i] == '(')
                count++;
        if(n % 2 || count * 2 > n) //不为偶数一定不合法，左括号数大于一般肯定不合法
            return "Impossible";
        int rest = n / 2 - count; //还需要补充多少左括号
        for(int i = 0; i < n; i++){
            if(brackets[i] == '?' && rest != 0){
                brackets[i] = '(';
                rest--;
            }
            else if(brackets[i] == '?')
                brackets[i] = ')';
        }
        int all = 0;
        for(int i = 0; i < n; i++){ //检查修改后内容是否合法
            if(brackets[i]  == '(')
                all++;
            else if(brackets[i] == ')')
                all--;
            if(all < 0)
                return "Impossible";
        }
        return brackets;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，三次单独的遍历
空间复杂度： $O(1)$ ，无额外空间