This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

leetcode Valid parentheses

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

 

Solution: You can use the first-in-last-out feature of the stack to compare whether a pair of parentheses is valid (an open parenthesis of the same type matches a close parenthesis of the same type), similar to (){}[], ({[]}), where an open parenthesis is expected to be followed by a close parenthesis of its type. So you can go through the string and see an open parenthesis character, push that open parenthesis on the stack, until you see a close parenthesis, push out an open parenthesis, see if it matches, if it doesn’t match, it’s not legal, otherwise keep going. First of all, there are pairs of valid parentheses, so we can check that the number of parentheses is not even, which will eventually be invalid, and then we can iterate through the string, and we’ll push any open parentheses we see, and we’ll pull out the last open parentheses we see if they match. Encountered in the process of traverse of the last one left parenthesis and met first right parenthesis must match, as the next right parenthesis on the affirmation and a left parenthesis matching, so use the stack can be convenient to judge, but is possible to meet right parenthesis, the stack before found that there is no element in the stack, the front has no left parenthesis to and its matching, Then the whole string is not valid.

class Solution {

    public boolean isValid(String s) {
        int len = s.length();
        // If the number of parentheses is not even then it must not be correct
        if (len % 2! =0) {
            return false;
        }
        char c;
        // use the stack first, then out
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < len; i++) {
            c = s.charAt(i);
            // open parentheses are pushed first
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
                continue;
            }// Empty stack indicates that there are no open parentheses in front of it
            if (stack.isEmpty()) {
                return false;
            }
            // If it is a close parenthesis, it will stack an open parenthesis to compare it with the current close parenthesis
            // The current parenthesis is), but the stack is not (
            if (c == ') '&& stack.pop() ! ='(') {
                return false;
            }// The current parenthesis is} but not {
            if (c == '] '&& stack.pop() ! ='[') {
                return false;
            }// The current parenthesis is] but the stack is not [
            if (c == '} '&& stack.pop() ! ='{') {
                return false; }}returnstack.isEmpty(); }}Copy the code

Or:

class Solution {

    public static Map<Character, Character> brackets;

    static {
        brackets = new HashMap<Character, Character>();
        brackets.put(') '.'(');
        brackets.put('} '.'{');
        brackets.put('] '.'[');
    }

    public boolean isValid(String s) {
        int len = s.length();
        // If the number of parentheses is not even then it must not be correct
        if (len % 2! =0) {
            return false;
        }
        char c;
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < len; i++) {
            c = s.charAt(i);
            // open parenthesis on the stack
            if (brackets.containsValue(c)) {
                stack.push(c);
                continue;
            }
            / / right parenthesis
            // Empty or off-stack elements do not match
            if(stack.isEmpty() || ! stack.pop().equals(brackets.get(c))) {return false; }}returnstack.isEmpty(); }}Copy the code