Click here to read more about algorithmic interviewing

Topic describes

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

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.

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

Stack + hash table solution

This is a simulation, same type of parenthesis, one close parenthesis for one open parenthesis.

It is not hard to find a solution that can be solved directly using stacks:

class Solution {
    HashMap<Character, Character> map = new HashMap<Character, Character>(){{
        put('] '.'[');
        put('} '.'{');
        put(') '.'(');
    }};
    public boolean isValid(String s) {
        Deque<Character> d = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                d.addLast(c);
            } else {
                if(! d.isEmpty() && d.peekLast() == map.get(c)) { d.pollLast(); }else {
                    return false; }}}returnd.isEmpty(); }}Copy the code

  • Time complexity: Scan the string S once. The complexity is O(n)O(n)O(n)

  • Space complexity: The hash table space used is fixed and does not increase with the increase of sample size. The complexity is O(1)O(1)O(1)

Note: Mitsuha is usedDequeDouble-endian queues act as stacks instead ofStack, which is what the JDK recommends. It is recommended that all Java students adopt itDequeAs a stack.

Do not useStackThe reason is thatStackInherited fromVectorHaving all the public apis for dynamic arrays is not secure, andStackIt also makes the mistake of object-oriented design: it treats composition as inheritance.

Stack + ASCII difference solution

We can also take advantage of the fact that the left and right parts of “()”, “{}”, and “[]” are close in ASCII values.

(and) correspond to -7 and -8 respectively; [and] correspond to 43 and 45 respectively; {and} correspond to 75 and 77 respectively.

So if you have the same type of parentheses, you have a difference of less than 2, and if you have different types of parentheses, you have a difference of more than 2.

With this feature, we can save a hash table:

class Solution {
    public boolean isValid(String s) {
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int u = c - '0';
            if (c == '(' || c == '{' || c == '[') {
                d.addLast(u);
            } else {
                if(! d.isEmpty() && Math.abs(d.peekLast() - u) <=2) {
                    d.pollLast();
                } else {
                    return false; }}}returnd.isEmpty(); }}Copy the code

  • Time complexity: Scan the string S once. The complexity is O(n)O(n)O(n)

  • Space complexity: O(1)O(1)O(1)

The last

This is the 20th article in our “Brush through LeetCode” series. The series started on 2021/01/01, and there are 1916 questions in LeetCode by the start date. Some of them have locks, so we will finish all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

As the number of LeetCode questions keeps increasing with weekly and biweekly competitions, in order to facilitate our progress statistics, we will calculate the progress according to the total number of questions at the beginning of the series as the denominator and the completed questions as the numerator. The current progress is 20/1916.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: Github address & Gitee address.

In the repository, you’ll see links to the series, the corresponding code for the series, the LeetCode source links, and some other preferred solutions.


# Algorithms and data structures

# LeetCode antithesis

# Algorithmic interview