0020.Valid-Parentheses

有效的括号

1. 题目

1.1. 描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

1.2. 示例

示例1:

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

1.3. 提示

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

2. 思路

【大意】括号匹配

2.1. 左括号进栈

• 创建数据结构栈，遍历字符串
• 遇到左括号则进栈
• 遇到右括号时
  • 栈为空返回false
  • 栈不为空，查找栈顶元素是否为对应左括号，匹配则左括号出栈继续遍历，不匹配则返回false
• 最后判断栈是否为空，空则为true
• 时间复杂度为O(n)，空间复杂度为O(n)

2.2. 右括号进栈

• 创建数据结构栈，遍历字符串
• 遇到左括号时将对应右括号压入栈
• 遇到右括号时直接判断与栈顶元素是否相等
• 时间复杂度为O(n)，空间复杂度为O(n)

2.3. 字符串为栈

• 将参数字符串s作为栈使用，使得空间复杂度为O(1)
• 时间复杂度为O(n)

3. 代码

3.1. C++

3.1.1. 左括号进栈

3.1.1.1. switch-case

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;

        for(int i=0;s[i]!='\0';i++){
            switch(s[i]){
                // 左括号就进栈
                case '[':
                case '{':
                case '(':
                    st.push(s[i]);
                    break;
                case ')':
                    // 栈空或栈顶不匹配
                    if(st.empty()||st.top()!='('){
                        return false;
                    } 
                    // 移除栈顶元素
                    st.pop();
                    break;
                case '}':
                    if(st.empty()||st.top()!='{'){
                        return false;
                    } 
                    st.pop();
                    break;
                case ']':
                    if(st.empty()||st.top()!='['){
                        return false;
                    } 
                    st.pop(); 
                    break;   
            }
        }
        return st.empty();
    }
};

3.1.1.2. if-else

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for(int i=0;s[i]!='\0';i++){
            if(s[i]=='['||s[i]=='{'||s[i]=='('){
                st.push(s[i]);
            }
            else{
                if(st.empty()){ return false; }
                char temp = st.top();
                if(s[i]==']'&&temp !='['){ return false; }
                if(s[i]=='}'&&temp !='{'){ return false; }
                if(s[i]==')'&&temp !='('){ return false; }
                st.pop();
            }
        }
        return st.empty();
    }
};

3.1.2. 右括号进栈

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for(int i=0;s[i]!='\0';i++){
            if(s[i]=='['){ st.push(']'); }
            else if(s[i]=='{'){ st.push('}'); }
            else if(s[i]=='('){ st.push(')'); }
            else{
                if(st.empty()||st.top()!=s[i]){ return false; }
                st.pop();
            }
        }
        return st.empty();
    }
};

3.1.3. 字符串为栈

class Solution {
public:
    bool isValid(string s) {
        // 指向栈顶
        int top = -1;

        for(int i=0;s[i]!='\0';i++){
            // 判断栈顶元素是否匹配当前字符，不匹配时入栈
            if(top<0||!isMatch(s[top],s[i])){
                s[++top]=s[i];
            }else{
                --top;
            }
        }
        return top==-1;
    }
    bool isMatch(char top,char ch){
        if(top=='['&&ch==']'){ return true; }
        if(top=='{'&&ch=='}'){ return true; }
        if(top=='('&&ch==')'){ return true; }
        return false;
    }
};

3.2. Java

3.2.1. 左括号进栈

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        for (char ch : s.toCharArray()) {
            if(ch=='['||ch=='{'||ch=='('){
                st.push(ch);
            }else{
                if(st.empty()){ return false; }
                char temp = st.peek();
                if(ch==']'&&temp!='['){ return false; }
                if(ch=='}'&&temp!='{'){ return false; }
                if(ch==')'&&temp!='('){ return false; }
                st.pop();
            }
        }
        return st.empty();
    }
}

3.2.2. 右括号进栈

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        for (char ch : s.toCharArray()) {
            if(ch=='['){ st.push(']'); }
            else if(ch=='{'){ st.push('}'); }
            else if(ch=='('){ st.push(')'); }
            else{
                if(st.empty()||st.peek()!=ch){ return false; }
                st.pop();
            }
        }
        return st.empty();
    }
}