Leetcode 20. Valid parentheses

20、 Valid parenthesis

1） Title Description

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

Valid string needs to meet ：

1. Opening parentheses must be closed with closing parentheses of the same type .
2. 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^4
• s Brackets only '()[]{}' form

2） analysis

Take advantage of the first in first out feature of the stack , Stack to solve the problem .

• Parentheses complete pairing , Then the string must be even length ;
• Traversal string , If it's left bracket , Then press the corresponding right parenthesis into the stack ;
• If it's a right parenthesis , Determine whether the characters at the top of the stack are equal to them , If not equal , return false;
• End of traversal , If the stack is empty , return true, Otherwise return to false.

3）C++ Code

class Solution {
    
public:
    bool isValid(string s) {
    
        if(s.length()%2)
            return false;
        stack<int> stk;
        for(int i=0;i<s.length();i++){
    
            if(s[i]=='(')
                stk.push(')');
            else if(s[i]=='[')
                stk.push(']');
            else if(s[i]=='{')
                stk.push('}');
            else if(stk.empty()||stk.top()!=s[i])
                return false;
            else
                stk.pop();
        }
        return stk.empty();
    }
};