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

一.题目描述
NC536迷失的括号
妹有括号序列brackets，因为过了太久，导致里面有些括号看不清了，所以用??代替，她想知道这个括号序列能不能恢复成合法的括号序列。具体操作是将??改为'('或者')'。brackets只由'?','(',')'构成。
合法的括号序列的定义：
1.空字符为合法括号序列
2.(+合法括号序列+) 为合法括号序列
3.()+合法括号序列为合法括号序列
如果能构造出来则返回恢复后任意合法的括号序列，否则返回Impossible
图片说明
二.算法(贪心)

首先讲一下博主对于这一题目的想法，博主开始是利用贪心+栈来处理这道题目的，但是调了很久就是处理不好贪心的问题，对于将?在什么时候转换为(，什么时候转换为)不好进行处理，最后只能换方法了(有写出来的也可以评论区告诉一下)。首先，对于括号匹配问题，我们并不采用栈而是通过计数器来处理：对于每一个字符从1到字符串长度n，考虑字符串前i个字符，如果左括号个数大于等于右括号个数，则前i个字符匹配成功。这里用到一个计数器sum，遍历到左括号sum++，遍历到右括号sum--，只要在遍历的过程中使sum小于0则不存在匹配，返回Impossbile。当全部遍历完成后，如果左括号个数等于右括号，即sum等于0，则整个字符串匹配成功。由于?可以转换成括号我们可以先计算出还缺少ans个左括号，基于贪心我们迫切将最左边ans个?替换为(，其余的?替换为)，转化为基础的括号匹配问题。下面给出完整代码：

class Solution {
public:
    string MissingBrackets(string brackets) {
        int a=0,b=0;
        for(int i=0;i<brackets.size();i++){
            if(brackets[i]=='(') a++;
            if(brackets[i]==')') b++;
        }
        if(a*2>brackets.size()||2*b>brackets.size()||brackets.size()%2==1) return "Impossible";
        int ans=brackets.size()/2-a;
        //需要转换成左括号的个数
        for(int i=0;i<brackets.size();i++){
            if(brackets[i]=='?'){
                if(ans>0){
                    ans--;
                    brackets[i]='(';
                } else {
                    brackets[i]=')';
                }
            }
        }
        int sum=0;
        //利用计数器sum来判断是否可以比配成功
        for(int i=0;i<brackets.size();i++){
            if (brackets[i]=='(') sum++;
            if (brackets[i]==')') sum--;
            if (sum<0) return "Impossible";
        }
        if(sum==0) return brackets;
        else return "Impossible";
    }
};

时间复杂度： $O(n)$ 只需要对字符数组进行一次遍历
空间复杂度： $O(n)$ 需要额外空间来建立字符数组
优缺点：贪心思路需要理解，代码实现简单
三.算法(java实现)
看没有人用javaAC的，下面来用java来实现。和算法二的思路一样，下面直接给出完整代码：

import java.util.*;
public class Solution {
    public String MissingBrackets (String brackets) {
        int a=0,b=0;
        char[] s=brackets.toCharArray();
        int len=brackets.length();
        for(int i=0;i<len;i++){
            if(s[i]=='(') a++;
            if(s[i]==')') b++;
        }
        int ans=len/2-a;
        //需要转换成左括号的个数
        for(int i=0;i<len;i++){
            if(s[i]=='?'){
                if(ans>0){
                    ans--;
                    s[i]='(';
                } else {
                    s[i]=')';
                }
            }
        }
        int sum=0;
        //利用计数器sum来判断是否可以比配成功
        for(int i=0;i<len;i++){
            if (s[i]=='(') sum++;
            if (s[i]==')') sum--;
            if (sum<0) return "Impossible";
        }
        String str=new String(s);
        if(sum==0) return str;
        else return "Impossible";
    }
}

时间复杂度： $O(n)$ 只需要对字符数组进行一次遍历
空间复杂度： $O(n)$ 需要额外空间建立字符数组
优缺点：贪心思路需要理解，代码实现没有c++简单，其中设计对String转换为字符数组，字符数组转成String