Valid bracket sequence of "Niuke | daily question"

Author's brief introduction ： One likes to write , Sophomore rookie of planning major

Personal home page ：starry Lu Li

First date ：2022 year 7 month 17 Sunday, Sunday

Last article ：『 Cattle guest | A daily topic 』 Pressure into the stack 、 Pop-up sequence _

Subscription column ：『 Collection of Niuke brush questions 』

Daily recommendation ： Basic algorithm is a very important part in both graduate interview and job interview , Here we recommend an algorithm interview artifact ： Cattle from - Interview artifact ; Algorithm problems can only be kept thinking and feeling by brushing more and more frequently , Let's move quickly （ reminder ： The common interview question bank is also very nice Oh ）

If the article helps you, remember to praise + Collect and support

1. A daily topic

2. Method 1： Left bracket in stack

2.1 Thought analysis

Traversal string , encounter '(','{','[' When these three characters , Put characters on the stack stk; And met ')','}',']' When these three characters are, the corresponding matching characters are sent out of the stack . The specific rules are as follows ：

• step 1： Introducing auxiliary stack stk, Traversal string , Every encounter '(','{','[' Put characters on the stack stk
• step 2： When you meet ')','}',']' When characters , Then check whether the stack is empty , And whether the top element is a matching element （ Such as { and } Match, etc ）, If the stack is empty or the top element of the stack is not a matching element, the bracket sequence is illegal
• step 3： When the stack is not empty , And the top element of the stack is a matching element , Then the element at the top of the stack will be released .
• step 4： Loop matching string , Until each character is processed
• step 5： Check stack stk Is it empty , If the stack is empty, the sequence is legal , Otherwise it's illegal （ When the parentheses are closed in the correct order, the last stack is empty ）

2.2 Core code

import java.util.*;
public class Solution {
    
    /** * @param s string character string  * @return bool Boolean type  */
    public boolean isValid (String s) {
    
        // write code here
        Stack<Character>stk=new Stack<Character>();
        int l=s.length();
        for(int i=0;i<l;++i){
    
            char a=s.charAt(i);
            if(a=='('||a=='['||a=='{')stk.push(a);
            if(a==')'){
    
                if(stk.isEmpty()||stk.peek()!='(') return false;
                stk.pop();
                continue;
            }
            if(a==']'){
    
                if(stk.isEmpty()||stk.peek()!='[')return false;
                stk.pop();
                continue;
            }
            if(a=='}'){
    
                if(stk.isEmpty()||stk.peek()!='{')return false;
                stk.pop();
                continue;
            }
        }
        return stk.isEmpty()?true:false;
    }
}

3. Method 2： Right parenthesis on the stack

3.1 Thought analysis

Still traversal string , With the help of auxiliary stack

• step 1： When you meet '(','[','{' When these three characters are, the corresponding matching characters are put on the stack ( They correspond to each other ')',']','}')
• step 2： When the character that appears is not '(','[','{' When these three characters , First judge whether the stack is empty or whether the current character is the same as the top element of the stack ,
• step 3： When the stack is empty or the current character is different from the character at the top of the stack , The sequence of parentheses is illegal , Go straight back to ;
• step 4： Otherwise the top element of the stack is pushed out . Traverse the string until all elements are traversed . Finally, judge whether the stack is empty , If it is not empty, the bracket sequence is illegal ; Otherwise, it is a legal sequence .

3.2 Core code

import java.util.Stack;

public class Solution {
    
    public boolean isValid(String s) {
    
		Stack<Character> stack = new Stack<Character>();
		// Use foreach loop 
		for (char c : s.toCharArray()) {
    
			if (c == '(')
				stack.push(')');
			else if (c == '{')
				stack.push('}');
			else if (c == '[')
				stack.push(']');
			else if (stack.isEmpty() || stack.pop() != c)
				return false;
		}
		return stack.isEmpty();
	}
}

Subscription column ：『 Collection of Niuke brush questions 』

Daily recommendation ： Basic algorithm is a very important part in both graduate interview and job interview , Here we recommend an algorithm interview artifact ： Cattle from - Interview artifact ; Algorithm problems can only be kept thinking and feeling by brushing more and more frequently , Let's move quickly （ reminder ： The common interview question bank is also very nice Oh ）

If the article helps you, remember to praise + Collect and support