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

题目描述
题目给出括号序列brackets，要求判断此序列是否合法。并且具体操作是将??改为'('或者')'。brackets只由'?','(',')'构成。
合法的括号序列的定义：
1.空字符为合法括号序列
2.(+合法括号序列+) 为合法括号序列
3.()+合法括号序列为合法括号序列

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

方法一：暴力求解

求解思路
对于本题目的求解，我们可以用暴力遍历的方法，首先我们声明两个变量，index变量记录问号出现的下标，dp变量记录两个问号之间括号的差值，正数表示差相应右括号，负数表示差相应绝对值的左括号。然后我们字符串进行遍历，并且将index和dp进行赋值，然后第二次遍历字符串，对每个问号所在的位置进行判断，如果存在左括号数加上差值都小于右括号则返回impossible，同理右括号也一样进行判断。最后对问号进行替换如果左括号多，则记录数大于0，从右向左进行右括号替换，同理右括号多的情况也按上述操作。最终我们即可通过暴力解法得到本题的答案。

图片说明

解题代码

class Solution {
public:
    string MissingBrackets(string brackets) {
        int n = brackets.length();
        if(n % 2) // 不为偶数一定不合法
            return "Impossible";
        vector<int> index; // index记录问号出现的位置
        vector<int> mydp; // 记录两个问号之间左右括号个数的差
        int a = 0; //维护两个问号之间左右括号个数的差
        for(int i = 0; i < n; i++)
        {   //找到？的位置，即之间的括号差
            if(brackets[i] == '?')
            {
                index.push_back(i); // 位置入数组
                mydp.push_back(a);
                a = 0;
            }
            else if(brackets[i] == ')') // 遇到左加，遇到右减
                a--;
            else
                a++;
        }
        index.push_back(n);
        mydp.push_back(a);
        n = index.size(); 
        a = 0;
        int q = 0; // 记录问号出现次数
        for(int i = 0; i < n; i++)
        {
            a += mydp[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)$
空间复杂度：使用辅助数组index[N],dp[N],因此空间复杂度为 $O(N)$

方法二：贪心思想求解

求解思路
对于本题我们也可以使用贪心的思想进行求解，对于合法的括号序列，左括号和右括号是相匹配的，因此我们可以从括号数入手，每次贪心地将差的左括号或者右括号补齐，最后验证整个序列是否合法。

图片说明

解题代码

class Solution {
public:
    string MissingBrackets(string brackets) {
        int n = brackets.length();
        int mycount = 0; // 存储括号数量
        for(int i = 0; i < n; i++) // 统计左括号数
            if(brackets[i] == '(')
                mycount++;
        if(n % 2 || mycount * 2 > n) // 不为偶数一定不合法，左括号数大于一般肯定不合法
            return "Impossible";
        int rest = n / 2 - mycount; // 还需要补充多少左括号
        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)$