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)
Top comments (0)