Problem Statement:
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
Example 4:
Input: s = “([])”
Output: true
Example 5:
Input: s = “([)]”
Output: false
Constraints:
1<= s.length <= 104sconsists of parentheses only'()[]{}'.
Approach:
- Use a stack to track opening brackets.
- Create a map that stores matching pairs →
{ : }, [ : ], ( : ). - Traverse the string:
- If it’s an opening bracket, push it onto the stack.
- If it’s a closing bracket, pop from the stack and check if it matches the expected closing bracket. If not,
return false.
- After processing, if the stack is empty → all brackets matched →
return true. Otherwise,return false.
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(n)
Dry Run
Input: s = "([{}])"
Step 0: Start Function isValid("([{}])")
stack = []
map = { "{" : "}", "[" : "]", "(" : ")" }
Iteration (i = 0): s[0] = "("
- "(" is in map → push to stack
- stack = ["("]
Iteration (i = 1): s[1] = "["
- "[" is in map → push to stack
- stack = ["(", "["]
Iteration (i = 2): s[2] = "{"
- "{" is in map → push to stack
- stack = ["(", "[", "{"]
Iteration (i = 3): s[3] = "}"
- "}" is not in map → pop from stack
- top = "{"
- Check s[3] == map[top] → "}" == map["{"] → "}" == "}" ✔
- stack = ["(", "["]
Iteration (i = 4): s[4] = "]"
- "]" is not in map → pop from stack
- top = "["
- Check s[4] == map[top] → "]" == map["["] → "]" == "]" ✔
- stack = ["("]
Iteration (i = 5): s[5] = ")"
- ")" is not in map → pop from stack
- top = "("
- Check s[5] == map[top] → ")" == map["("] → ")" == ")" ✔
- stack = []
Loop ends (i == s.length)
Final Check:
stack.length === 0 → true
Return true
Output: true
var isValid = function(s){
let stack = [];
let map = {
"{" : "}",
"[" : "]",
"(" : ")"
}
for(let i=0; i < s.length; i++){
if(map[s[i]]) {
stack.push(s[i]);
}
else {
let top = stack.pop();
if(!top || s[i] != map[top]) {
return false;
}
}
}
return stack.length === 0;
}
def isValid(s: str) -> bool:
stack = []
pairs = {'{': '}', '[': ']', '(': ')'}
for ch in s:
if ch in pairs:
stack.append(ch)
else:
if not stack:
return False
top = stack.pop()
if ch != pairs[top]:
return False
return len(stack) == 0
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
Map map = new HashMap<>();
map.put('{', '}');
map.put('[', ']');
map.put('(', ')');
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c != map.get(top)) return false;
}
}
return stack.isEmpty();
}
}
#include <string>
#include <vector>
#include <unordered_map>
bool isValid(const std::string &s) {
std::vector stack;
std::unordered_map map = {
{'{', '}'},
{'[', ']'},
{'(', ')'}
};
for (char c : s) {
if (map.count(c)) {
stack.push_back(c);
} else {
if (stack.empty()) return false;
char top = stack.back();
stack.pop_back();
if (c != map[top]) return false;
}
}
return stack.empty();
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isValid(const char *s) {
size_t n = strlen(s);
char *stack = (char*)malloc(n + 1);
if (!stack) return 0; // allocation failed, treat as invalid
int topIndex = 0;
for (size_t i = 0; i < n; ++i) {
char c = s[i];
if (c == '{' || c == '[' || c == '(') {
stack[topIndex++] = c;
} else {
if (topIndex == 0) { free(stack); return 0; }
char top = stack[--topIndex];
if (!(
(top == '{' && c == '}') ||
(top == '[' && c == ']') ||
(top == '(' && c == ')')
)) {
free(stack);
return 0;
}
}
}
int result = (topIndex == 0) ? 1 : 0;
free(stack);
return result;
}
using System;
using System.Collections.Generic;
public class Solution {
public bool IsValid(string s) {
var stack = new Stack();
var map = new Dictionary {
{'{', '}'},
{'[', ']'},
{'(', ')'}
};
foreach (char c in s) {
if (map.ContainsKey(c)) {
stack.Push(c);
} else {
if (stack.Count == 0) return false;
char top = stack.Pop();
if (c != map[top]) return false;
}
}
return stack.Count == 0;
}
}
