Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

A valid string must meet the following requirements:

  1. An open parenthesis must be closed with a close parenthesis of the same type.
  2. The left parentheses must be closed in the correct order.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string can be considered a valid string.

Note that an empty string is also considered valid.

Example 1:

Input:"()"Output:true
Copy the code

Example 2:

Input:"[the] {} ()"Output:true
Copy the code

Example 3:

Input:"(]"Output:false
Copy the code

Example 4:

Input:"([]"Output:false
Copy the code

Example 5:

Input:"{[]}"Output:true
Copy the code

Answer:

Very simple problem, the string each character on the stack, simple judgment can be. Such as:

Input:"{[]}"The initial stack is empty,'{'Pushes the top element of the next character stack'{'with'['Do not match,'['Pushes the top element of the next character stack'['with'] 'Match,'['Unstack the top element of the next character on the stack'{'with'} 'Match,'} 'The stack is empty. Returns TrueCopy the code

The key is to determine whether the characters match, and the criteria for matching are the opposite parenthesis characters, not the same characters. You can use switch to determine three bracket characters, or three IF statements, or you can use hash tables to map bracket relationships.

Java:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();// Initialize the stack
        for (char b : s.toCharArray()) {
            switch (b) {
                case '(': {
                    stack.push(') ');
                    break;
                }
                case '{': {
                    stack.push('} ');
                    break;
                }
                case '[': {
                    stack.push('] ');
                    break;
                }
                default: {// Return false in case of mismatch
                    if(stack.isEmpty() || stack.pop() ! = b) {return false; }}}}return stack.isEmpty();// If the stack is empty, all matches are proved, and return true, otherwise false}}Copy the code

Python:

Note: There is no switch in Python… case… Statement, official let use if judgment instead of…

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c == '[':
                stack.append('] ')
            elif c == '(':
                stack.append(') ')
            elif c == '{':
                stack.append('} ')
            elif len(stack) == 0 orstack.pop() ! = c:return False
        return len(stack) == 0
Copy the code

Welcome to wechat. Common name: Love to write bugs