Aunt Guan is participating in the “Java Theme month – Java brush question clocking”, see the activity link for more details

First of all, I want to clarify that every algorithm problem has multiple solutions, and we’ll just talk about a few excellent solutions in LeetCode ~, hopefully

Can help you, that we first look at the topic description ~

I. Title Description:

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string. Example: the input: “()” output: true input: “() [] {}” output: true input: “[]” input output: false: “([]” input output: false: “{[]}” output: true

Ii. Analysis of Ideas:

We know that a valid parenthesis must be one open parenthesis for one close parenthesis; And nested parentheses, the first opening parentheses, are followed by the corresponding closing parentheses. In other words, as we walk through the string, the first open parenthesis that comes up is the last one to determine if it has a corresponding close parenthesis. Do you think of stacks in this order? Stack is advanced after the ah, we can put the traversal of the brackets in the stack, and then meet with the corresponding right parenthesis, take out the left parenthesis on the top of the stack instead of judging whether the same type, until after the completion of the traversal, see whether there are elements on the stack, if there is the specification, not all corresponding brackets, is invalid. If it does not exist, it means that all parentheses have been matched, and it is valid. Also, parentheses are paired, so when the string length is odd, it must be invalid. With that in mind, let’s write code:

Iii. Code demonstration:

public boolean isValid(String s) { int len = s.length(); If (len % 2 == 1){return false; if(len % 2 == 1){return false; } // Use map to save characters map <Character, Character> map = new HashMap<>(); map.put(')', '('); map.put(']', '['); map.put('}', '{'); / / initialize the stack, used to store the first traverse the left parenthesis preserved left parenthesis is / / why? Because a pair of parentheses must be left parenthesis before, but we cannot be sure how nested layers of brackets, therefore, to keep the left parenthesis first, then by traversal to right parenthesis to obtain the corresponding left parenthesis. Deque<Character> Deque = new LinkedList<>(); for (int I = 0; I < len;  i++) { char ch = s.charAt(i); if(map.containsKey(ch)){ if(deque.isEmpty() || deque.peek() ! = map.get(ch)){ return false; } deque.pop(); }else{ deque.push(ch); } } return deque.isEmpty(); }Copy the code

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together