Abstract: Last in first out is very important, we must make the last in first out clear. The stack is a cache, where uncertain items are stored first and the results are determined before being taken out. A stack is a dynamic linear data structure.

Answer key | “power button” 20 questions: effective brackets

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

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.

Example 1:

Input: s = "()" output: trueCopy the code

Example 2:

Input: s = "()[]{}" Output: trueCopy the code

Example 3:

Input: s = "(]" Output: falseCopy the code

Example 4:

Input: s = "([)]" Output: falseCopy the code

Example 5:

Input: s = "{[]}" Output: trueCopy the code

Tip:

• 
  $1 <= s.length <= 10^4$
• sOnly by brackets'[] {} ()'composition

Analysis of ideas:

Make “last in, first out” clear.

• When traversing the open parenthesis, a corresponding close parenthesis must be matched to the right of it. Therefore, parentheses with uncertain results need to be “cached” first;
• By the nature of the problem, the parentheses that are traversed later match first, so the current scenario is the data structure “stack”.

Reference Code 1:

import java.util.ArrayDeque;
import java.util.Deque;


public class Solution {

    public boolean isValid(String s) {
        int len = s.length();
        // Special case judgment
        if ((len % 2) = =1) {
            return false;
        }

        char[] charArray = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : charArray) {
            switch (c) {
                case '(':
                    stack.addLast(') ');
                    break;
                case '[':
                    stack.addLast('] ');
                    break;
                case '{':
                    stack.addLast('} ');
                    break;
                default:
                    if(stack.isEmpty() || stack.removeLast() ! = c) {return false;
                    }
                    break; }}returnstack.isEmpty(); }}Copy the code

Reference Code 2:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public boolean isValid(String s) {
        int len = s.length();
        if (len == 0) {
            return true;
        }
        // The odd length must not be valid parentheses
        if ((len % 2) = =1) {
            return false;
        }

        char[] charArray = s.toCharArray();
        Map<Character, Character> hashMap = new HashMap<>();
        hashMap.put(') '.'(');
        hashMap.put('] '.'[');
        hashMap.put('} '.'{');

        Deque<Character> stack = new ArrayDeque<>();
        for (char c : charArray) {
            // If traversed to the close parenthesis, check for a match
            if (hashMap.containsKey(c)) {
                // The stack is empty and the top of the stack does not match the current are not "valid"
                if(stack.isEmpty() || ! hashMap.get(c).equals(stack.removeLast())) {return false; }}else {
                // add to the stack when traversing to the left parenthesisstack.addLast(c); }}returnstack.isEmpty(); }}Copy the code