题意理解

给定一个字符串，由()?组成，?可以代替为(或者)，判断能否在替换后，使得字符串变成是括号合法的，若可以则随意输出一种合法的结果。
括号合法的要求：
1.空字符为合法括号序列
2.(+合法括号序列+) 为合法括号序列
3.()+合法括号序列为合法括号序列

方法一

首先，对于基础的括号匹配问题，我们通过以下方法判断其可以匹配：
对于所有i，从1到字符串长度n，考虑字符串前i个字符，如果左括号个数大于等于右括号个数，则前i个字符匹配成功。这里用到一个计数器all，遇到左括号all++，遇到右括号all--，若某时刻all小于0则匹配失败了。
最后i==n时，如果左括号个数等于右括号，即all等于0，则整个字符串匹配成功。

对于该题中存在？的情况，我们可以先计算出还缺少need个左括号，然后将最左边need个？替换为(，其余的？替换为），转化为基础的括号匹配问题。
其中，求出need之后我们可以通过n是否为偶数、左括号的个数是否小于等于n/2，来提前判断该字符串是否能转化为匹配的括号序列。

至于为什么将最左边need个？替换为(。因为左括号越早的出现，该字符串最终匹配的概率越大，而且我们只需要输出一种正确的括号序列即可。这里是贪心的思想。

示意图如下：
图片说明
具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param brackets string字符串 brackets
     * @return string字符串
     */
    string MissingBrackets(string brackets) {
        int left_count, right_count, n=brackets.size();
        for (int i=0;i<n;i++) {
            if (brackets[i]=='(') left_count++;
            if (brackets[i]==')') right_count++;
        }
        //从括号的个数和字符串的奇偶性判断是否可能。
        if (left_count*2>n || right_count*2>n || n%2==1) return "Impossible";
        //用need记录还需要几个左括号，而且左括号尽可能更早地出现在左边
        int need = n/2-left_count;
        for (int i=0;i<n;i++) {
            if (brackets[i]=='?') {
                if (need>0) {
                    need--;
                    brackets[i]='(';
                }
                else brackets[i]=')';
            }
        }
        //all来判断是否出现了右括号多于左括号的情况
        int all=0;
        for (int i=0;i<n;i++) {
            if (brackets[i]=='(') all++;
            if (brackets[i]==')') all--;
            //注意每次操作后都要判断一下
            if (all<0) return "Impossible";
        }
        if (all==0) return brackets;
        else return "Impossible";
    }
};

时间复杂度： $O(n)$ 。所有的循环都是单重循环字符串。
空间复杂度： $O(1)$ 。仅仅开辟了常数个数的变量。

方法二

（1）对于字符串进行遍历，记录？出现的位置放在数组x中，以及与上一个？之间左括号比右括号多a个，放在数组y中。
（2）对于每个？所在的位置进行判断，如果之前出现的左括号个数（可以加上之前出现的？，假装这些？替换为左括号）大于等于右括号，则暂时匹配成功；否则返回Impossible。注意，这里a是要根据y数组更新的。
（3）最后开始对？进行替换。如果左括号多，则从右往左，先替换为右括号，再依次右括号、左括号得替换；如果右括号多，则对称操作。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param brackets string字符串 brackets
     * @return string字符串
     */
    vector<int> x,y;//x记录？出现的位置，y记录两个？之间左右括号个数的差
    int diff=0, ap=0;//diff记录左括号和右括号的差值

    bool judge(int len) {
        int count = 0, i=0;//count记录？出现的次数。
        while(i<len) {
            diff = diff + y[i];//更新diff
            if(-diff > count)
                return false;
            count++;
            i++;
        }
        if(-diff > x.size() - 1) 
            return false;
        return true;
    }

    string MissingBrackets(string brackets) {
        // write code here
        if (brackets.size() % 2) return "Impossible";
        int len=brackets.size();
        for(int i=0;i<len;i++){
            if(brackets[i]=='?'){
                x.push_back(i);
                y.push_back(diff);
                diff=0;
                ap++;
            }
            else if(brackets[i]==')') diff--;
            else diff++;
        }
        x.push_back(len);
        y.push_back(diff);
        len = x.size();
        diff = 0;

        //遍历？的位置，判断把当前？变为左括号时，到此的字符串是否匹配。
        if (!judge(len)) return "Impossible";

        //最后把？转化为左右括号
        if(diff>0){ //左括号多于右括号
            diff++;
            for(int i=len-2;i>=0;i--){
                //从最后开始遍历
                if(diff>0){
                    brackets[x[i]]=')';
                    diff--;
                }
                else{
                    diff++;
                    brackets[x[i]]='(';
                }
            }
        }
        else{ //右括号多于左括号
            diff--;
            for(int i=0;i<len-1;i++){
                //从前开始遍历
                if(diff<0){
                    diff++;
                    brackets[x[i]]='(';
                }
                else{
                    diff--;
                    brackets[x[i]]=')';
                }
            }
        }
        return brackets;
    }
};

时间复杂度： $O(n)$ 。所有的循环都是单重循环字符串。
空间复杂度： $O(n)$ 。创建了x和y数组用来记录，每个数组的最大长度为字符串的长度。

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

题意理解

方法一

方法二