题解 | #合法的括号字符串#

合法的括号字符串

http://www.nowcoder.com/practice/eceb50e041ec40bd93240b8b3b62d221

题目的主要信息：

给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:

左括号'('必须有对应的右括号')'
右括号')'必须有对应的左括号'('
左括号必须在对应的右括号前面
*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符
空字符串也视为合法的括号字符串

方法一：

正序和倒序遍历两遍，分别把星号当做左括号和右括号。

从左往右遍历，把星号视为左括号，在遍历的过程中如果出现左括号数量比右括号少，表示该字符串不合法，返回false；
从右往左遍历，把星号视为右括号，在遍历的过程中如果出现右括号数量比左括号少，表示该字符串不合法，返回false。

两次遍历均通过，说明该字符串合法，返回true。

具体做法：

class Solution {
public:
    bool isValidString(string s) {
        int n=s.size();
        int flag=0;//flag用于判断是否合法
        //从左往右遍历一遍
        for(int i=0;i<n;i++){//将*视为左括号
            if(s[i]==')'){//如果当前字符是右括号则flag--
                flag--;
                if(flag<0){//如果右括号个数比左括号多则不合法
                    return false;
                }
            }else{//如果当前字符是左括号或*则flag++
                flag++;
            }
        }
        flag=0;
        //从右往左遍历一遍
        for(int i=n-1;i>=0;i--){//将*视为右括号
            if(s[i]=='('){//如果当前字符是左括号则flag--
                flag--;
                if(flag<0){//如果左括号个数比左括号多则不合法
                    return false;
                }
            }else{//如果当前字符是右括号或*则flag++
                flag++;
            }
        }
        return true;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历字符串。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

用栈进行判断。left栈保存左括号的下标，star栈保存星号的下标，遍历一遍字符串，遇到左括号就把左括号的下标进栈，遇到星号就把星号的下标进栈，如果是右括号就进行匹配，首先和左括号匹配，如果没有左括号就和星号匹配，如果两个都匹配失败，说明字符串非法。

遍历结束后再对多余的左括号和星号进行判断。如果左括号尚未匹配完，而星号已经在左括号左边了，那么左括号将无法配对，说明字符串非法。如果左括号全部匹配成功，则该字符串合法。 alt 具体做法：

class Solution {
public:
    bool isValidString(string s) {
        stack<int> left;//保存左括号的下标
        stack<int> star;//保存星号的下标
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){//左括号的下标进栈
                left.push(i);
            }else if(s[i]=='*'){//星号的下标进栈
                star.push(i);
            }else if(s[i]==')'){//右括号进行匹配
                if(!left.empty()){//先和左括号匹配
                    left.pop();
                }else if(!star.empty()){//如果左括号匹配失败则和星号匹配
                    star.pop();
                }else {//匹配不成功，字符串非法
                    return false;
                }
            }
        }
        //右括号全部匹配成功，判断左括号和星号是否合法
        while(!left.empty()&&!star.empty()){
            int lt=left.top();
            int st=star.top();
            left.pop();
            star.pop();
            if(st<lt){//星号如果不在左括号右边，非法
                return false;
            }
        }
        if(left.empty()){
            return true;
        }else return false;
    }
};

复杂度分析：