Leetcode 20 Valid Parentheses
The key of solving this problem is to use a stack. Whenever we see an open parenthesis we push it to the stack, when we see an close parenthesis we check if it matches the latest one in the stack, if it does we pop the latest one from the stack, otherwise we push it to the stack.
At the end we just need to check if the stack is empty.
Solution
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let stack = [];
for(let i = 0; i < s.length; i++) {
const c = s[i];
let lastParenthes = stack[stack.length - 1]
if(c === ')' && lastParenthes === '(') {
stack.pop()
} else if(c === ']' && lastParenthes === '[') {
stack.pop()
} else if(c === '}' && lastParenthes === '{') {
stack.pop()
} else {
stack.push(c)
}
}
return stack.length === 0
};Time complexity is O(n). Space complexity is O(1)