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:

1. Open brackets must be closed by the same type of brackets.
2. 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
        Stack stack = 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
        stack stk;
        
        // 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 Stack stack = 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; } } }