Solution For Valid Parentheses
Problem Description:
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 that an empty string is also considered valid.
Example:
Input: “()[]{}”
Output: true
Solution Approach:
This problem can be solved using a stack data structure. We can process the string character by character and push every opening bracket onto the stack. Whenever we encounter a closing bracket, we can check if the top of the stack matches the corresponding opening bracket. If it does, we can pop the opening bracket from the stack. If it doesn’t match, we return false since the string is not valid.
At the end, if the stack is empty, it means all brackets are properly terminated, thus our string is valid, otherwise, the string is invalid.
Here is the solution in Python:
“`python
class Solution:
def isValid(self, s: str) -> bool:
stack = [] # initializing our stack
brackets = {‘(‘: ‘)’, ‘{‘: ‘}’, ‘[‘: ‘]’} # a hash-map to quickly compare opening and closing brackets
for char in s:
if char in brackets: # if we have a opening bracket, append it to our stack
stack.append(char)
elif stack and brackets[stack[-1]] == char: # if we have a closing bracket, check if the top of the stack has a matching opening bracket
stack.pop()
else: # if we have a unexpected character
return False
return not stack # returns true only if the stack is empty
“`
Time and Space complexity:
The time complexity of this algorithm is O(n) since we process each character in the input string once. The space complexity is also O(n) since in a worst-case scenario, we might need to store all the opening brackets in the stack.
Step by Step Implementation For Valid Parentheses
class Solution { public boolean isValid(String s) { // create a stack to store opening parentheses Stackstack = new Stack<>(); // loop through the string for (int i = 0; i < s.length(); i++) { // get the current character char c = s.charAt(i); // if the current character is an opening parentheses if (c == '(' || c == '{' || c == '[') { // push it onto the stack stack.push(c); } // if the current character is a closing parentheses else if (c == ')' || c == '}' || c == ']') { // if the stack is empty, return false if (stack.isEmpty()) { return false; } // pop the top element from the stack char top = stack.pop(); // if the current character and the top element from the stack don't match, return false if (c == ')' && top != '(' || c == '}' && top != '{' || c == ']' && top != '[') { return false; } } } // if the stack is not empty at the end, return false if (!stack.isEmpty()) { return false; } // return true return true; } }
def isValid(s): # Initialize a stack to be used in the algorithm. stack = [] # Hash map for keeping track of mappings. This keeps the code very clean. # Also makes adding more types of parenthesis easier mapping = {")": "(", "}": "{", "]": "["} # For every character in the input string for char in s: # If the character is an closing bracket if char in mapping: # Pop the topmost element from the stack, if it is non empty # Otherwise assign a dummy value of '#' to the top_element variable top_element = stack.pop() if stack else '#' # The mapping for the opening bracket in our hash and the top # element of the stack don't match, return False if mapping[char] != top_element: return False else: # We have an opening bracket, simply push it onto the stack. stack.append(char) # In the end, if the stack is empty, then we have a valid expression. # The stack won't be empty for cases like ((() return not stack
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 that an empty string is also considered valid. function isValid(s) { // create a stack to store opening parentheses let stack = []; // create a map to store mappings of parentheses let map = { '(': ')', '[': ']', '{': '}' }; // loop through string for (let i = 0; i < s.length; i++) { // if character is an opening parenthesis, push it to the stack if (s[i] === '(' || s[i] === '[' || s[i] === '{') { stack.push(s[i]); } // if character is a closing parenthesis else { // if stack is empty or character doesn't match the top of the stack, return false if (stack.length === 0 || map[stack.pop()] !== s[i]) { return false; } } } // return true if stack is empty return stack.length === 0; }
class Solution { public: bool isValid(string s) { // create a stack to store the opening parentheses stackstk; // iterate through the string for (char c : s) { // if we encounter an opening parenthesis, push it onto the stack if (c == '(' || c == '[' || c == '{') { stk.push(c); } // if we encounter a closing parenthesis... else { // if the stack is empty, then this is an invalid parenthesis if (stk.empty()) { return false; } // pop the top element off the stack char top = stk.top(); stk.pop(); // if the top element doesn't match the closing parenthesis, then this is an invalid parenthesis if (c == ')' && top != '(') { return false; } if (c == ']' && top != '[') { return false; } if (c == '}' && top != '{') { return false; } } } // if the stack is not empty at the end, then this is an invalid parenthesis return stk.empty(); } };
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace valid_parentheses { class Program { static void Main(string[] args) { Console.WriteLine(IsValid("()[]{}")); Console.WriteLine(IsValid("(]")); Console.WriteLine(IsValid("([)]")); Console.ReadKey(); } public static bool IsValid(string s) { //Create a stack to store opening parentheses Stackstack = new Stack (); //Loop through each character in the string for (int i = 0; i < s.Length; i++) { //If the character is an opening parenthesis, push it onto the stack if (s[i] == '(' || s[i] == '[' || s[i] == '{') { stack.Push(s[i]); } //If the character is a closing parenthesis else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { //If the stack is empty, that means there were more closing parentheses than opening, so the string is invalid if (stack.Count == 0) { return false; } //If the character is a closing parenthesis that doesn't match the top of the stack, the string is invalid else if (stack.Peek() == '(' && s[i] != ')' || stack.Peek() == '[' && s[i] != ']' || stack.Peek() == '{' && s[i] != '}') { return false; } //Otherwise, pop the top of the stack (since it's a match) and continue checking else { stack.Pop(); } } //If we've made it through the entire string and the stack is empty, the string is valid return stack.Count == 0; } } }