For 3 minutes a day, take the algorithmic counterattack route.

Handled in the collection

A daily collection of LeetCode preambles

Code warehouse

Making: github.com/meteor1993/…

Gitee: gitee.com/inwsy/LeetC…

Title: Valid parentheses

Title source: leetcode-cn.com/problems/va…

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid.

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.

Note that an empty string can be considered a valid string.

Example 1:

Input: "()" Output: trueCopy the code

Example 2:

Input: "()[]{}" Output: trueCopy the code

Example 3:

Input: "(]" Output: falseCopy the code

Example 4:

Input: "([)]" output: falseCopy the code

Example 5:

Input: "{[]}" Output: trueCopy the code

Their thinking

How to solve the problem?

Ah bah, there is a P solution, I tell you oh, this kind of problem has not seen, you just can’t think of it.

After thinking for a few minutes, I capitulated decisively and went to see the answer. This thing was not my kind of novice white guy.

As a result, one look at the answer seconds understand.

The whole idea of solving the problem is to borrow the data structure “stack” of the “first in, last out” characteristics.

So the first thing I want to do is think about the limiting cases, like if it’s an empty string, you can return true, and if it’s an odd string length, then obviously the left and right parentheses aren’t going to work.

Then comes the core question, one open parenthesis and one close parenthesis, maybe separated by thousands of mountains and rivers, how do you deal with that?

Using the stack structure:

  • When an open parenthesis is encountered, push it onto the stack.
  • When a close parenthesis is encountered, it is compared with the left parenthesis at the top of the stack.
  • If the match is successful, it may be nested within other matching brackets, so pop the left bracket at the top of the current stack.
  • If at the end of the day, there are no left elements on the stack, so there are no open parentheses left, then we’ve matched, and the parentheses string is valid. Otherwise, the match fails and the parenthesis string is invalid.

If the above paragraph is confusing, use the following GIF (source: LeetCode) :

Code implementation

With the above ideas, writing code is a trivial matter, let’s look at one of my own, completely in line with the above logic:

public boolean isValid(String s) {
    if (s.length() == 0) return true;

    if (s.length() % 2= =1) return false;

    Stack<Character> stack = new Stack<> ();

    for (int i = 0; i < s.length(); i++) {
        char charAt = s.charAt(i);

        // If it is an open parenthesis, the character is pushed onto the stack
        if (charAt == '(' || charAt == '{' || charAt == '[')
            stack.push(charAt);
        else {
            // If there are close parentheses and no open parentheses in the stack
            if (stack.isEmpty()) return false;
            // Get the top value of the stack
            char top = stack.peek();
            // Unstack if the value at the top of the stack is equal to the closing bracket, otherwise return false
            if ((top == '{' && charAt == '} ') || (top == '(' && charAt == ') ') || (top == '[' && charAt == '] '))
                stack.pop();
            else
                return false; }}return stack.isEmpty();
}
Copy the code

I don’t have to explain it any more because it’s already fairly clear.

Then I looked at the official answer, which basically kept the same idea as my code, except that I put the left and right parentheses into the hash table, and the hash table determines whether the parentheses exist.

private Map<Character, Character> map;

// Initialize the hash table
public Solution(a) {
    this.map = new HashMap<> ();
    this.map.put(') '.'(');
    this.map.put('} '.'{');
    this.map.put('] '.'[');
}


public boolean isValid_1(String s) {
    if (s.length() == 0) return true;

    if (s.length() % 2= =1) return false;

    Stack<Character> stack = new Stack<> ();

    for (int i = 0; i < s.length(); i++) {
        char charAt = s.charAt(i);
        // If it is not a close parenthesis, the character is pushed onto the stack
        if (!this.map.containsKey(charAt)) {
            stack.push(charAt);
        } else {
            // If there are close parentheses and no open parentheses in the stack
            if (stack.isEmpty()) return false;
            // Get the top value of the stack
            char top = stack.peek();
            // Unstack if the value at the top of the stack is equal to the closing bracket, otherwise return false
            if (top == this.map.get(charAt))
                stack.pop();
            else
                return false; }}return stack.empty();
}
Copy the code

Because there is too little data in the hash table and not enough addressing, the hash table scheme also appears to be more time-consuming than the sequential matching scheme.

Is there a more efficient solution, of course, directly using the array to simulate the stack on and off the stack, this time can be compressed within 1ms, the execution time can beat 100% of the users in Java submission, this example I will not write, interested students can write to see.

When I looked over the answer, I saw a 1ms solution, which was an optimization of the 2ms code I had before. It was interesting. Let’s talk about it:

public boolean isValid_2(String s) {
    char[] chs = s.toCharArray();
    Stack<Character> stack = new Stack<>();
    for (char c : chs) {
        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();
}
Copy the code

The solution is to put a corresponding close parenthesis inside the stack when the open parenthesis is encountered. The reason for doing this, I guess, is to check the value of the open parenthesis with the current loop. If the value is equal, the loop continues.

I have to say that the idea of this scheme is very clever, and the existing scheme has been optimized to reduce the time further. Sure enough, the ginger is still hot, your uncle is still your uncle.

Sure enough, there is no end to learning. I hope that if you brush LeetCode, if you have enough time, you can also look at different answers, which is really helpful to broaden your mind and vision.

By the way, I would like to make a joke: it’s crazy to think of these schemes. This brain circuit is too far from normal people. I can accept using array to reduce the time to less than 1ms, but I can optimize the scheme of stack data structure to less than 2ms, which I really believe.