## DEV Community is a community of 731,460 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Kaitian Xie

Posted on • Updated on

# Stack (Optimized)

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

int ptr = 0;
char[] map = new char[s.length()];

for (char ch : s.toCharArray()) {
switch (ch) {
case '(':
case '{':
case '[':
map[ptr++] = ch;
break;
case ')':
if (ptr == 0 || map[--ptr] != '(')
return false;
break;
case '}':
if (ptr == 0 || map[--ptr] != '{')
return false;
break;
case ']':
if (ptr == 0 || map[--ptr] != '[')
return false;
break;
}
}

return ptr == 0;
}
``````

This problem can be solved by using a stack. The solution provided by LeetCode uses the `Stack` class. However, it can be simulated by an array. First, we create an empty array `map` that has the same size as the string `s`. Then we iterate through each character of `s` and when we encounter a left parenthesis, we store the parenthesis in `map` at the `ptr` index. Also, we increment `ptr` by one. (similar to `push` in `Stack`). If we encounter a right parentesis, we check if the right parenthesis has a corresponding left parenthesis stored at `ptr -1` in `map`. If not, return `false`. Finally, we check if the `ptr` equals 0 (similar to an empty `Stack`).

Time Complexity: `O(n)`

Extra Space: `O(n)`