20. Valid brackets

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the 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.

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

The sample1:

Input:"()"

Output:true

    

The sample2:

Input:"[the] {} ()"

Output:true

    

The sample3:

Input:"(]"

Output:false

    

The sample4:

Input:"([]"

Output:false

    

The sample5:

Input:"{[]}"

Output:true

Copy the code

Method 1: stack

Algorithm idea:

Make use of the “in and out” feature of the stack, traverse each character of the input string, judge that the current ({[is the symbol on the right, then the symbol on the left is pushed into the stack. Continue to traverse, then out of the stack for judgment.

Reference code:

class Solution {

    / / stack

    public boolean isValid(String s) {

        if (s == null || s.length() == 0) {

            return true;

        }

        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {

            if (ch == '(') stack.push(') ');

            else if (ch == '{') stack.push('} ');

            else if (ch == '[') stack.push('] ');

            else if(stack.isEmpty() || ch ! = stack.pop())return false;

        }

        return stack.isEmpty();

    }

}

Copy the code

Complexity analysis:

  • Time complexity:, is the length of the string.
  • Space complexity: is the space used by the stack.