This is the 17th day of my participation in Gwen Challenge

preface

The valid brackets for question 20 are shown below:

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

A valid string must meet the following requirements:

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

A, thinking

When I saw this one-to-one matching problem, my first thought was to use stacks. Because the stack’s data structure is first in and last out, it is well suited for this type of problem.

The left parenthesis refers to ‘(‘ ‘{‘ ‘[‘, and the right parenthesis refers to ‘)’ ‘}’ ‘]’ for easy description

We just need to push when we hit an open parenthesis, and push when we hit a matching close parenthesis. If the stack is not empty at the end, it is not a valid string, if it is empty, it is a valid string.

Graphic access stack

Let’s take a slightly more complicated example here, assuming the string s = ‘((())()}’, as shown below.

The orange part is a string, and the part left blank indicates that it has been consumed (probably by pushing it onto the stack or matching the open parenthesis). The green part is the stack number representing the position of the element in the stack or string

Because the opening parenthesis is pushed, the first three characters are pushed at first, as shown below:

The fourth element in s is the close bracket, and it looks to see if it matches the element at the top of the stack, and if it does, it goes off the stack. In this case, the fourth element is), and the top element of the stack is (, and the stack is pushed out of the stack. As shown below:

The fifth element of S is still a close bracket and matches the top of the stack. As shown below:

The sixth element of S is an open parenthesis

The seventh element of S is a close bracket and can match the top of the stack, continuing off the stack. As shown below:

The eighth element of S is a close bracket, but does not match the top of the stack. Whenever such a mismatch occurs, the string is incorrect. Because positions 2 to 6 can be matched, if positions 1 to 8 cannot be matched, the string is not valid.

Second, the implementation

Implementation scheme

The implementation code

    public boolean isValid(String s) {
        String leftBrackets = "{[(";
        String rightBrackets = "})";
        Stack<String> stack = new Stack<>();
        for (int i=0; i<s.length(); i++) {
            String temp = s.substring(i, i+1);
            // with an open parenthesis, push
            if (leftBrackets.contains(temp)) {
                stack.push(temp);
            }
            // close parenthesis, unstack
            if (rightBrackets.contains(temp)) {
                if (stack.empty())
                    return false;
                int index = rightBrackets.indexOf(temp);
                String currentStr = stack.pop();
                if(! currentStr.equals(leftBrackets.substring(index, index+1))) {
                    return false; }}}return stack.empty();
    }
Copy the code

The test code

    public static void main(String[] args) {
        new Number20().isValid({() ()] "");
    }
Copy the code

The results of

The result was not very good, only beat 30%

Optimization scheme

Using char instead of String and removing string.indexof () as a reference to the shorter solution

Code implementation

    /** * uses a stack to implement */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            // open parenthesis, push
            if ('(' == c || '[' == c || '{' == c) {
                stack.push(c);
            } else {    // Close parenthesis out of the stack
                // If the stack is empty, return false
                if (stack.empty())
                    return false;
                if(! isMatch(stack.pop(), c)) {return false; }}}return stack.empty();
    }

    public boolean isMatch(char left ,char right) {
        switch (left) {
            case '{':
                return '} ' == right;
            case '(':
                return ') ' == right;
            case '[':
                return '] ' == right;
            default:
                return false; }}Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥