题意理解

给定一个字符串,由()?组成,?可以代替为(或者),判断能否在替换后,使得字符串变成是括号合法的,若可以则随意输出一种合法的结果。
括号合法的要求:
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";
    }
};

时间复杂度:。所有的循环都是单重循环字符串。
空间复杂度:。仅仅开辟了常数个数的变量。

方法二

(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;
    }
};

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