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<Character> stack = new Stack<Character>();
char top = ' ';
int len = str.length();
for (int i = 0; i < 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)