LeetCode parentheses matching I came across this question from LeetCode OJ where I am given a string containing parentheses and I need to find out if the string contains valid matching parentheses or not.


  Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
  
  The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.


This is the code I wrote (it got accepted and passed all the test cases.)

/** Java program to check if input string contains matching parameters 
    or not.
 *  @author     :       Anish
 *  @date       :       01-11-2017
 */
 import java.util.Stack;

 class Solution
 {
    public boolean isValid(String str)
    {
        Stack&lt;Character&gt; stack  =   new Stack&lt;Character&gt;();

        char top    =   ' ';
        int len     =   str.length();

        for (int i = 0; i &lt; len; i++)
        {
            char ch    =   str.charAt(i);

            if (ch == '(')
                stack.push(')');

            else if (ch == '[')
                stack.push(']');

            else if (ch == '{')
                stack.push('}');

            else if (!stack.empty())
            {
                top   =   stack.peek();

                if (top == ch)
                    stack.pop();
                else
                    stack.push(ch);
            }
            else if (stack.empty())
            {
                stack.push(ch);
            }
        }
        if (stack.empty())
        {
            return true;
        }
        return false;
    }
 }


ANALYSIS

Time Complexity : \$O(n)\$

Run Time : 9ms (on the leetcode OJ)

ISSUES


Even though my time is \$O(n)\$, yet my percentile is 70.4 which effectively means there are better and faster solutions out there. In that case, how do I optimize the above code to make it faster?
I have been using the Stack API provided by Java to solve the problem. Rather, if I were to redesign my own stack API and then use it to solve the problem, would I get faster runtime and better performance?
If the above point is true, then does it mean that in general, user designed APIs are faster than what is provided by the Java libraries? (assuming the user designed API is clean and bug free)
Usage of Stack

Don't use a Stack. This class is very old, it's thread safe (which you don't need) and achieves it by synchronizing the push and pop methods, which will have an impact in performance.

I would use ArrayDeque. By default it's initialized with size 16. To reduce number of re-allocations, allocate a larger size, perhaps ou can guess how many elements you'll need based on the size of the string. For example:

Queue&lt;Character&gt; queue = new ArrayDeque&lt;&gt;(str.size()/2);


Boxing of char

Note that each time you push/pop from the queue, you are boxing and unboxing char (to Character). For ultimate performance, create a char[] queue, but then you'll have to manage resizes and pointers to the top element yourself.

Fail fast

Consider that the input is {(])}. When finding ], your program can already know that the string is invalid and stop iterating. This will make the processing of invalid inputs potentially much faster.
So what about replace this:

else if (!stack.empty())
{
  top   =   stack.peek();
  if (top == ch)
    stack.pop();
  else
    stack.push(ch);
  }
  else if (stack.empty())
  {
    stack.push(ch);
  }
}
else if (stack.empty())
{
  stack.push(ch);
}


by:

else if (!stack.empty())
{
  top   =   stack.peek();
  if (top == ch)
    stack.pop();
  else
    return false; // quit
  }
}
else 
{
    return false; //quit
}


I didn't test and I might be missing something, but it looks that as soon as you have an char not matching the expected closing parenthesis, you can  conclude that it's invalid.

My suggestion

This has all the previous points applied and runs much faster:

public boolean isValid(String str) {
char[] stack = new char[str.length()];
int p = -1;

for (int i = 0; i &lt; str.length(); i++) {
  char ch = str.charAt(i);

  if (ch == '(') {
    stack[++p] = ')';
  } else if (ch == '[') {
    stack[++p] = ']';
  } else if (ch == '{') {
    stack[++p] = '}';
  } else if (p &gt;= 0) {
    char top = stack[p];

    if (top == ch) {
      p--;
    } else {
      return false;
    }
  } else {
    return false;
  }
}

return p &lt; 0;
}


EDIT: Benchmarks

I'm adding the results of benchmarks done with JMH with some different solutions to show how performance is impacted.

I used one valid input: ([[{{([[{{[[[[]]]]}}]])}}]]) and one invalid input: ([[{{([[{{[[[[]]]]}}]]})}}]]).

Parameters of the benchmark:

# Warmup: 5 iterations, 1 s each
# Measurement: 5 iterations, 1 s each
# Benchmark mode: Average time, time/op (nanoseconds)


Results:

Benchmark               (input)  Mode  Cnt    Score    Error  Units
Benchmark.finalSolution   valid  avgt    5   67.468 ±  1.411  ns/op
Benchmark.finalSolution invalid  avgt    5   53.832 ±  1.543  ns/op

Benchmark.toCharArray     valid  avgt    5  241.692 ± 11.705  ns/op
Benchmark.toCharArray   invalid  avgt    5  261.955 ±  6.192  ns/op

Benchmark.original        valid  avgt    5  245.888 ±  3.329  ns/op
Benchmark.original      invalid  avgt    5  265.483 ±  3.312  ns/op

Benchmark.useArrayDeque   valid  avgt    5  100.597 ±  1.621  ns/op
Benchmark.useArrayDeque invalid  avgt    5  102.695 ±  0.659  ns/op

Benchmark.useLinkedList   valid  avgt    5  180.679 ±  4.395  ns/op
Benchmark.useLinkedList invalid  avgt    5  190.591 ±  4.010  ns/op