Problem Statement: Valid Parentheses
Given a string 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.
Note:
- An empty string is considered valid.
- You may assume that the input string contains only the characters
(,),{,},[, and].
Example:
Input:
"()"
Output:
True
Input:
"()[]{}"
Output:
True
Input:
"(]"
Output:
False
Input:
pythonCopy code"([)]"
Output:
pythonCopy codeFalse
Input:
"{[]}"
Output:
True
Approach:
The problem is best solved using a stack data structure. The stack allows us to keep track of opening parentheses, and we can check whether the most recent opening parenthesis matches the closing parenthesis as we iterate through the string.
- Iterate through the String:
- For each character in the string:
- If it is an opening bracket (
'(','{', or'['), push it onto the stack. - If it is a closing bracket (
')','}', or']'), check if the stack is not empty and if the top element of the stack is the matching opening bracket.- If they match, pop the top element from the stack.
- If they don’t match or the stack is empty, the string is invalid.
- If it is an opening bracket (
- For each character in the string:
- Final Check:
- After processing all characters, if the stack is empty, then the string is valid, meaning all opening brackets had matching closing brackets in the correct order.
- If the stack is not empty, there are unmatched opening brackets, so the string is invalid.
Time Complexity:
- Time Complexity: O(n)O(n)O(n), where nnn is the length of the input string. We iterate through the string once and perform constant-time operations (push/pop) on the stack.
- Space Complexity: O(n)O(n)O(n) in the worst case, where all characters could be opening brackets (stack could hold all nnn characters).
Code Implementation
C Code:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isValid(char* s) {
int len = strlen(s);
char stack[len];
int top = -1;
for (int i = 0; i < len; i++) {
char ch = s[i];
if (ch == '(' || ch == '{' || ch == '[') {
stack[++top] = ch;
} else {
if (top == -1) return false; // Stack is empty, unmatched closing bracket
char topElement = stack[top--];
if ((ch == ')' && topElement != '(') ||
(ch == '}' && topElement != '{') ||
(ch == ']' && topElement != '[')) {
return false; // Mismatched parentheses
}
}
}
return top == -1; // If the stack is empty, it's a valid string
}
int main() {
char s[] = "()[]{}";
printf("Is valid: %s\n", isValid(s) ? "True" : "False"); // Output: True
return 0;
}
C++ Code:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Solution {
public:
bool isValid(string s) {
stack<char> stack;
for (char ch : s) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else {
if (stack.empty()) return false; // If stack is empty, no matching opening parenthesis
char top = stack.top();
stack.pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false; // Mismatched parentheses
}
}
}
return stack.empty(); // If stack is empty, all parentheses matched
}
};
int main() {
Solution solution;
cout << (solution.isValid("()[]{}") ? "True" : "False") << endl; // Output: True
return 0;
}
Java Code:
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else {
if (stack.isEmpty()) return false; // Stack is empty, no matching opening parenthesis
char top = stack.pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false; // Mismatched parentheses
}
}
}
return stack.isEmpty(); // If stack is empty, all parentheses matched
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.isValid("()[]{}")); // Output: true
}
}
Python Code:
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack # If stack is empty, all parentheses matched
# Example Usage
solution = Solution()
print(solution.isValid("()[]{}")) # Output: True
C# Code:
using System;
using System.Collections.Generic;
public class Solution {
public bool IsValid(string s) {
Stack<char> stack = new Stack<char>();
foreach (char ch in s) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.Push(ch);
} else {
if (stack.Count == 0) return false; // Stack is empty, no matching opening parenthesis
char top = stack.Pop();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false; // Mismatched parentheses
}
}
}
return stack.Count == 0; // If stack is empty, all parentheses matched
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.IsValid("()[]{}")); // Output: True
}
}
JavaScript Code:
var isValid = function(s) {
const stack = [];
const mapping = {')': '(', '}': '{', ']': '['};
for (let char of s) {
if (char in mapping) {
let top = stack.pop() || '#';
if (mapping[char] !== top) return false;
} else {
stack.push(char);
}
}
return stack.length === 0;
};
console.log(isValid("()[]{}")); // Output: true
Explanation:
- Iterate through the string: We loop over each character in the string. If the character is an opening bracket (
(,{,[), we push it onto the stack. - Check for closing brackets: If the character is a closing bracket (
),},]), we check whether the stack is empty. If it is, the parentheses are mismatched, so we returnfalse. If the stack is not empty, we pop the top element and check if it matches the corresponding opening bracket. - Return result: After processing all characters, if the stack is empty, then the parentheses are correctly matched, so we return
true. If the stack is not empty, it means there are unmatched opening brackets, so we returnfalse.
Edge Cases:
- Empty string: An empty string is considered valid, so the function should return
truefor"". - Unmatched brackets: If there are unmatched brackets or the brackets are in the wrong order (e.g.,
([)]), the function should returnfalse. - Single type of bracket: A string with only one type of bracket (e.g.,
(((((((((())))))or[[[[[[[[]]]]]]]]]) should also be handled correctly.
Time Complexity:
- Time Complexity: O(n)O(n)O(n), where nnn is the length of the input string. We process each character once and perform constant-time operations (push/pop) for each character.
- Space Complexity: O(n)O(n)O(n) in the worst case for the stack, where nnn is the length of the string.
Summary:
The problem is efficiently solved using a stack, which allows us to track the opening brackets and check if they match the closing brackets in the correct order. This ensures that the string is valid if and only if all opening parentheses are properly closed and nested.