Leetcode notes 20. valid parentheses

Title Description

Topic linking

Given one only includes ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ String s , Determines whether the string is valid .

Valid string needs to meet ：

Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .

Example 1：

Input ：s = “()”
Output ：true
Example 2：

Input ：s = “()[]{}”
Output ：true
Example 3：

Input ：s = “(]”
Output ：false
Example 4：

Input ：s = “([)]”
Output ：false
Example 5：

Input ：s = “{[]}”
Output ：true

Tips ：

1 <= s.length <= 10⁴
s Brackets only ‘()[]{}’ form

Ideas

This is the classic stack subject , The essence of valid parentheses , That is, at the corresponding level , Correspondence between brackets , If there are no brackets corresponding or different brackets at the same level , Is determined to be invalid brackets . This is related to stack The behavior of entering and leaving the stack completely conforms to .

Code

class Solution {
    
public:
    bool isValid(string s) {
    
        stack<char> front;
        for(char i : s)
        {
    
            if(i == '(' || i == '[' || i == '{')
            {
    
                front.push(i);
            }
            else{
    
                if(front.empty())
                {
    
                    return false;
                }
                char top = front.top();
                front.pop();
                if((i == ')' && top != '(') || (i == ']' && top != '[') || (i == '}' && top != '{'))
                {
    
                    return false;
                }
            }
        }
        if(front.empty())
        return true;
        else return false;
    }
};

Be careful

1. It's going on stack Of top Before extraction , Be sure to judge empty situation , Otherwise, it is extremely easy to appear runtime error The situation of .
2. Pay attention to special situations , That is, there is only one bracket , This special case of the very underworld .