【LeetCode】2. Valid parentheses · valid parentheses

Title Description

Description in English

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

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.

English address

https://leetcode.com/problems/valid-parentheses/https://leetcode.com/problems/valid-parentheses/

Description of Chinese version

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

Constraints· Tips ：

1 <= s.length <= 104

s Brackets only '()[]{}' form

Address of Chinese version

https://leetcode.cn/problems/valid-parentheses/https://leetcode.cn/problems/valid-parentheses/

Their thinking

Because it needs to be closed in sequence , That is, the first right parenthesis needs to be paired with the nearest left parenthesis , And there are no left or right parentheses left at the end , Therefore, we can take advantage of the first in and last out feature of the stack structure , Push unpaired parentheses onto the stack , Every time you read a new bracket , Just check whether it matches the top element , If it matches, the element at the top of the stack will pop up , If there is no match, the current element will be put on the stack , Then go on to the next , Until there are no new elements , If the stack is empty at this time , Then the string is valid , Otherwise, it is invalid .

How to solve the problem

My version

    public static boolean isValid(String s) {
        Stack stack = new Stack();
//        stack.push(s.charAt(0));
        //  Get the ASCII Code value 
        int parenthesesLeft = Integer.valueOf('(');
        int parenthesesRight = Integer.valueOf(')');
        int middleBracketLeft = Integer.valueOf('[');
        int middleBracketRight = Integer.valueOf(']');
        int curlyBracketLeft = Integer.valueOf('{');
        int curlyBracketRight = Integer.valueOf('}');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int value = Integer.valueOf(c);
            //  Get the ASCII code 
            char peek;
            int peekValue;
            //  The left half is directly stacked , Check whether the right half matches the top element 
            if (value == parenthesesLeft || value == middleBracketLeft || value == curlyBracketLeft) {
                stack.push(c);
                continue;
            } else if (value == parenthesesRight || value == middleBracketRight || value == curlyBracketRight) {
                if (stack.isEmpty()) {
                    return false;
                }
                peek = (char) stack.peek();
                peekValue = Integer.valueOf(peek);
                if (value == parenthesesRight) {
                    if (peekValue == parenthesesLeft) {
                        stack.pop();
                        continue;
                    }
                } else if (value == middleBracketRight) {
                    if (peekValue == middleBracketLeft) {
                        stack.pop();
                        continue;
                    }
                } else if (value == curlyBracketRight) {
                    if (peekValue == curlyBracketLeft) {
                        stack.pop();
                        continue;
                    }
                }
                return false;
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }

Official edition

public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {
   {
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

Students with better methods are welcome to poke in the comment area *〜（ゝ.∂）～～～