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

The title information

Given one that only includes'('.') '.'{'.'} '.'['.'] 'S to determine 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.Copy the code

Example 1:

Enter: s ="()"Output:true
Copy the code

Example 2:

Enter: s ="[the] {} ()"Output:true
Copy the code

Example 3:

Enter: s ="(]"Output:false
Copy the code

Example 4:

Enter: s ="([]"Output:false
Copy the code

Their thinking

Think of matching between brackets as finding an object, with the open bracket (regardless of whether it is a curly bracket or a curly bracket) as a girl and the close bracket as a boy, because the boy has to actively match the open bracket. And look for an object to pay attention to the right eye, have a feeling. Also look for the girl closest to you who doesn’t have an object (unmatched left parenthesis). If the closing bracket matches one of the open brackets, then they’re in, and the next guy’s turn. Until all the boys are gone. If there’s anyone left at this point, male or female. It’s all left over, not enough to make everyone happy. Need to return false. Return true if there is nothing left and everyone has found their love interest.

There is another case, which is the example above4The closest left parenthesis is'.['. This guy likes black and long and straight, but his latest girl has short hair. This guy's freaking out, not talking about it, not talking about it, not talking about it. I'm going to return false.Copy the code

If we look at the ASCII comparison table, we see that the ASCII values of the brackets are either 1 or 2 apart. This information will be used later.

Specific to the code, you can use the stack to solve. I’m going to go through the string that they gave me, and if it’s an open bracket (girl) it’s going to be on the stack, if it’s a close bracket, it’s going to be a boy. See if the bracket matches the top of the stack. If it does, it pops out the element at the top of the stack. If it doesn’t, it returns false. At the end, check to see if the stack is empty, if it is, everyone is happy, return true, if not, return false. Going back to the ASCII table above, if two brackets match, their ASCII differences must be no more than 2. You can write code if you know that.

Implementation code:

class Solution {
    public boolean isValid(String s) {
    Stack<Character> stack=new Stack<> ();
        for(int i=0; i<s.length (); i++){char ch=s.charAt (i);
            if(ch=='(' || ch=='{' || ch=='['){
                stack.add (ch);
            }else {
                if(! stack.empty () && Math.abs (stack.peek ()-ch)<=2){
                    stack.pop ();
                }else {
                    return  false; }}}returnstack.isEmpty (); }}Copy the code