Topic describes

This is the 20. Valid parentheses on LeetCode, and the difficulty is easy.

Key words: stack, hash table

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 <= 104
  • sOnly by brackets'[] {} ()'composition

Their thinking

Determine the validity of parentheses: We typically use the stack (first in, last out) data structure to solve the problem.

When iterating through a character, we can first compare the left parenthesis ([{push into the stack, close parenthesis)]} with the top element to see if it matches. If the match succeeds, the left parenthesis is pushed out of the stack, otherwise the close parenthesis is pushed onto the stack. If it’s a string with valid parentheses, the stack is empty at the end, so we can just tell if the stack is empty at the end.

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2= =1) {
            // If it is odd, the return is not consistent
            return false;
        }

        // Create a hash table to store the values of parentheses, paying attention to matching and parity
        HashMap<Character, Character> map = new HashMap(3);
        map.put(') '.'(');
        map.put('] '.'[');
        map.put('} '.'{');

        // Initialize a stack object
        Stack stack = new Stack();
        // Iterate over the string
        char[] cs = s.toCharArray();
        for (char c : cs) {
            if (map.containsKey(c)) {
                // If it is a close parenthesis
                if(stack.isEmpty() || stack.peek() ! = map.get(c)) {// If it is empty or the closing parenthesis does not match the opening parenthesis, it fails
                    return false;
                } else{ stack.pop(); }}else {
                // if the parenthesis is left, it will be pushed directlystack.push(c); }}// If the stack is empty at the end, it is a perfect match and successful
        returnstack.isEmpty(); }}Copy the code

reference

My Github repository has been set up synchronously, click access