Algorithm
Problem Name: 20. Valid Parentheses
Problem URL: https://leetcode.com/problems/valid-parentheses/
Level: Easy
Details:
We'll use Stack Data structure to solve this Leetcode Valid Parentheses problem
Details:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()" Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]" Output: false
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
/**
* Is Valid Parenthesis
*
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
const parenthesis = {
'(' : ')',
'{' : '}',
'[' : ']',
};
const stack = [];
for(let i = 0; i < s.length; i++) {
const charParen = s[i];
if (Object.keys(parenthesis).includes(charParen)) {
stack.push(charParen)
} else {
const startParen = Object.keys(parenthesis).find(key => parenthesis[key] === charParen);
if (stack?.[stack.length - 1] === undefined) {
return false;
}
if (stack?.[stack.length - 1] === startParen) {
stack.pop();
} else {
return false;
}
}
}
if (stack.length === 0) {
return true;
}
return false;
};
Input
Output
#2 Code Example with C Programming
Code -
C Programming
bool isValid(char* s) {
int l;
char *stack, c;
int sp = 0;
if (!s || !*s) return true;
l = strlen(s);
stack = malloc(l * sizeof(char));
while (c = *s ++) {
switch (c) {
case '(':
case '{':
case '[':
stack[sp ++] = c;
break;
case ')':
if (sp == 0 || stack[-- sp] != '(') { free(stack); return false; }
break;
case '}':
if (sp == 0 || stack[-- sp] != '{') { free(stack); return false; }
break;
case ']':
if (sp == 0 || stack[-- sp] != '[') { free(stack); return false; }
break;
default:
break;
}
}
free(stack);
return sp == 0 ? true : false;
}
Input
Output
#3 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool isValid(string s) {
stackstk;
for(auto c: s){
if(stk.empty() && (c == ')' || c == ']' || c == '}')) return false;
if(c == '(' || c == '[' || c == '{') stk.push(c);
else{
char left = stk.top();
if((c == ')' && left != '(') || (c == ']' && left != '[') || (c == '}' && left != '{')) return false;
stk.pop();
}
}
return stk.empty();
}
};
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _020_ValidParentheses
{
public bool IsValid(string s)
{
var stack = new Stack < char>();
foreach (var ch in s)
{
if (ch == '(' || ch == '[' || ch == '{')
stack.Push(ch);
else if (ch == ')' || ch == ']' || ch == '}')
{
if (stack.Count < = 0) return false;
var lastCh = stack.Peek();
if ((ch == ')' && lastCh == '(') ||
(ch == ']' && lastCh == '[') ||
(ch == '}' && lastCh == '{'))
stack.Pop();
else
return false;
}
}
return stack.Count == 0;
}
}
}
Input
Output
#5 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isValid(String s) {
Deque stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.add(c);
} else {
if (stack.isEmpty()) {
return false;
}
char popped = stack.removeLast();
if (!((c == ')' && popped == '(') || (c == ']' && popped == '[') || (c == '}' && popped == '{'))) {
return false;
}
}
}
return stack.isEmpty();
}
}
Input
Output
#6 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isValid(self, s):
brackets_stack, lefts, rights = [], ("(", "[", "{"), (")", "]", "}")
for char in s:
if char in lefts:
brackets_stack.append(char)
elif not brackets_stack or lefts.index(brackets_stack.pop()) != rights.index(char):
return False
return not brackets_stack
Input
Output
Demonstration
Leetcode - 20. Valid Parentheses solution in Javascript