Station B true question: how to judge whether brackets are valid?

Today's question is not only the real question of BiliBili's written test this year, but also a classic interview question about stack.

After studying the previous article, I think many friends have seen it. What I want to write next is a series of articles on "algorithm diagram", which may be interspersed with a small number of other types of articles, but "algorithm and data structure" will be the key content of my article output this year.

When I write this algorithm series, I will pay attention to two problems:

Let's first review the content of "stack" in previous periods:

Then, let's move on to today's official content

subject

Given a string that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.

Valid strings must meet:

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Problem solving ideas

This problem is to verify the symmetry of parentheses. For example, the string "([{}])" is correct and should return true, while the string "([{})]" is wrong and should return false.

As can be seen from the above topic, parentheses are divided into three categories: parentheses, brackets and braces. Then we can take advantage of the first in and last out feature of the stack, Put all the left parentheses ("(", "[", "{") into the stack first, and then when you encounter the right parenthesis, match it with the elements at the top of the stack. For example, when you encounter ")", if the top of the stack is "(", it indicates that the matching is successful, and the elements at the top of the stack exit the stack, and then continue the process of character string circulation. If there is a matching error, it will directly return false.

Suppose we want to match the string "([])" is it legal? Then the execution process is like this.

First encounter the left parenthesis and put it on the stack first:

@H_ 502_ 149@

Then let's use code to realize the whole process

Implementation code I

public boolean isValid(String s) {
    int slen = s.length(); // 括号的长度
    if (slen % 2 == 1) { // 括号不是成对出现直接返回 false
        return false;
    }
    // 把所有对比的括号存入 map，对比时用
    Map<Character,Character> map = new HashMap<>();
    map.put(')','(');
    map.put('}','{');
    map.put(']','[');
    // 定义栈，用于存取括号（辅助比较）
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < slen; i++) { // 循环所有字符
        char c = s.charAt(i);
        if (map.containsKey(c)) { // 为右边的括号，如 ')'、'}' 等
            if (stack.isEmpty() || stack.peek() != map.get(c)) { // 栈为空或括号不匹配
                return false;
            }
            stack.pop(); // 是一对括号，执行出栈（消除左右括号）
        } else { // 左边括号，直接入栈
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

We submit the following code in leetcode, and the execution results are as follows:

Code parsing

The map set of the above code is a matching rule used to define parentheses, For example, the matching value corresponding to ")" is "(", and the matching value of "]" is "[", and then we cycle the string to be verified. When we encounter the left bracket, we directly put it on the stack, and when we encounter the right bracket, we make it match with the top element of the stack. When the whole string cycle ends, if the stack is empty, it indicates that the bracket of the string is legal.

Complexity analysis

Time complexity: O (n), traversing the whole string. Space complexity: O (n).

Implementation code 2

In addition to using the stack, we can also use the replace method in Java to eliminate parentheses in the string. For example, we can cycle to replace "()" or "[]" or "{}" with empty. Finally, if the string is empty after execution, it indicates that the parentheses in the string are legal. The specific implementation code is as follows:

public boolean isValid(String s) {
        int len;
        do {
            len = s.length();
            // 消除成双成对的符号
            s = s.replace("()","").replace("[]","").
                    replace("{}","");
        } while (len != s.length()); // 不能再进行替换了，replace 方法没有替换任何字符
        return s.length() == 0;
    }

We submit the following code in leetcode, and the execution results are as follows:

From the operation results, the difference in execution efficiency between the two is still obvious: