Valid brackets (force deduction 20)

Catalog

One 、 Title Description

Two 、 Train of thought explanation

3、 ... and 、Java Code implementation  

Four 、C++ Code implementation  

5、 ... and 、 Time and space complexity analysis  

---

 

One 、 Title Description

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 <= 104
s Brackets only '()[]{}' form

Two 、 Train of thought explanation

         The problem of valid bracket classes can basically be solved by stack , Because the matching order of parentheses is just in line with the stack's first in, last out feature .

         Traversal string , When you have an open parenthesis , It into the stack ; When you encounter a close bracket , Just pop up , If the pop-up bracket does not match the current right bracket , It means something is wrong .

        After traversing the string , If the stack is not empty , It means that there is a left parenthesis , Description error ; If the stack is empty , The match is correct .

        It can also be simplified ： If you encounter a left bracket , Just press the corresponding right bracket （ For example, meet '(', Just press in ')' ）. When you encounter the closing parenthesis, you only need to pop up the element , Just compare whether the pop-up element is consistent with the current bracket , In this way, a few if Judge .

3、 ... and 、Java Code implementation  

class Solution {
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(c=='('){
                stack.push(')');
            } else if(c=='['){
                stack.push(']');
            } else if(c=='{') {
                stack.push('}');
            } else if(stack.isEmpty() || stack.pop()!=c){
                return false;
            }
        }

        // If the stack is not empty , It means that there is a left parenthesis ; If the stack is empty , Description brackets are correct 
        return stack.isEmpty();        
    }
}

 

Four 、C++ Code implementation  

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

5、 ... and 、 Time and space complexity analysis  

        Time complexity ：        O(N)

        Spatial complexity ：        O(N)