Leetcode skimming: stack and queue 03 (valid parentheses)

20. Valid parenthesis

Force button topic link

Given one only includes ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ String , Determines whether the string is valid .

Valid string needs to meet ：

• Opening parentheses must be closed with closing parentheses of the same type .
• The left parenthesis must be closed in the correct order .
• Note that an empty string can be considered a valid string .

Example 1:

• Input : “()”
• Output : true

Example 2:

• Input : “()[]{}”
• Output : true

Example 3:

• Input : “(]”
• Output : false

Example 4:

• Input : “([)]”
• Output : false

Example 5:

• Input : “{[]}”
• Output : true

Obviously, with the idea of stack

package com.programmercarl.stacks_queues;

import java.util.Stack;

/** * @ClassName IsValid * @Descriotion TODO * @Author nitaotao * @Date 2022/6/29 13:41 * @Version 1.0 **/
public class IsValid {
    
    public boolean isValid(String s) {
    
        /** *  Obviously, this problem is done by stack  */
        Stack stack = new Stack();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
    
            // The left symbol is added to the stack 
            if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') {
    
                stack.push(chars[i]);
            } else {
    
                // If it starts directly with a right parenthesis , return false
                if (stack.size() == 0) {
    
                    return false;
                }
                char item = (char) stack.pop();
                switch (item) {
    
                    case '(':
                        if (chars[i] != ')') {
    
                            return false;
                        }
                        break;
                    case '[':
                        if (chars[i] != ']') {
    
                            return false;
                        }
                        break;
                    case '{':
                        if (chars[i] != '}') {
    
                            return false;
                        }
                        break;
                }
            }
        }
        return stack.size() == 0;
    }
}

I have done this before , Look at the thought at that time .

class Solution {
    
   public boolean isValid(String s) {
    
        String[] arr = s.split("");
        if (arr.length % 2 != 0) {
    
            // If it's not even , There must be a mismatch 
            return false;
        }
        // ( [ {  To advance  ) ] } For out 
        LinkedList queue = new LinkedList(); // The stack structure 
// for (int i = 0; i < arr.length; i++) {
    
// System.out.print(arr[i]);
// }
// System.out.println();
        for (int i = 0; i < arr.length; i++) {
    
            if (arr[i].equals("{") || arr[i].equals("[") || arr[i].equals("(")) {
    
                queue.addFirst(arr[i]);
            } else {
    
                // If the first one is the right bracket 
                if (queue.size() == 0) {
    
                    return false;
                }
                String left = (String) queue.remove();


                if (left.equals("{")) {
    
                    if (arr[i].equals("}")) {
    
                        continue;
                    } else {
    
                        return false;
                    }
                } else if (left.equals("[")) {
    
                    if (arr[i].equals("]")) {
    
                        continue;
                    } else {
    
                        return false;
                    }
                } else if (left.equals("(")) {
    
                    if (arr[i].equals(")")) {
    
                        continue;
                    } else {
    
                        return false;
                    }
                }
            }
        }
        if (queue.size() != 0) {
    
            return false;
        }
        return true;
    }
}

hhhhhh, At that time, violent thoughts , Still too young .