Algorithm problem – Valid parentheses in strings

Leetcode link: leetcode-cn.com/problems/va…

Topic describes

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

A valid string must meet the following requirements:

An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses 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

1

Subject analysis

Such as the validity of the judgment of the topic is often stack to operate is very convenient, we can think of the following analysis

Create a Stack and a Map. The Map stores three key-value pairs “()”, “[]”, and “{}”

Then we go through each character in the string, get the character value, and compare the character value we get with the character key at the top of the stack. If the character key at the top of the stack corresponds to the value value1==value in the Map, that is considered a valid pair of parentheses and the top character is pushed off the stack. Otherwise, the character value is pushed onto the stack.

If the Stack is empty after a traversal, the string is a valid parenthesis.

The problem solving code

class Solution {
    public boolean isValid(String s) {
        if(s.length()==0) {return true;
        }
        Map<Character,Character> map = new HashMap();// Create a map to store key-value pairs
        Stack<Character> stack = new Stack();// Create a stack to store characters in a string
        map.put('('.') ');
        map.put('['.'] ');
        map.put('{'.'} ');
        for(int i=0; i<s.length(); i++){ Character indexChar = s.charAt(i);if(! stack.isEmpty()){char temp = stack.peek();
                Character value = map.get(temp);
                if(value! =null&&value==indexChar){// If the value corresponding to the top character is not empty and the value is equal to the item in the traversal, the top character is removed from the stack
                    stack.pop();
                }else{
                    stack.push(indexChar);// Otherwise, the parent and child are being traversed}}else{
                stack.push(indexChar);// empty stack}}return stack.isEmpty();// If the stack is empty, the string is legal parenthesis}}Copy the code

2

This idea of solving the problem is not meaningful enough to be adopted in practical application. It can be viewed on demand

The ASCII characters in parentheses (){}[] are: 40, 41, 123, 125, 91, 93

So we’re still using the stack

The difference between the character c1 in the string traversed and the character c2 at the top of the stack must be satisfied that b=c1-c2, b>0 and b<3, if the two are guaranteed to be a pair of valid parentheses, otherwise it is not satisfied

There is a huge increase in efficiency because there is less Map building

The problem solving code

class Solution {
    public boolean isValid(String s) {
        //"(){}[]" asciit values are 40, 41, 123, 125, 91, 93 respectively
        Stack<Character> stack = new Stack();
        for(int i=0; i<s.length(); i++){if(stack.isEmpty()){// If the stack is empty, the stack is pushed directly
                stack.push(s.charAt(i));
                continue;
            }
            char indexChar = s.charAt(i);// Get the characters in the string
            Character stackChar = stack.peek();// Get the top of the stack
            if(stackChar==null||indexChar==stackChar){// If the top character of the stack is empty, or the two characters are the same, the traversed string is pushed directly into the stack
                stack.push(indexChar);
            }else{
                int b = indexChar-stackChar;
                if(b<3&&b>0) {// If the difference between the iterated character and the string at the top of the stack is enough to commit, the element at the top of the stack is removed
                    stack.pop();
                }else{ stack.push(indexChar); }}}returnstack.isEmpty(); }}Copy the code