Valid Parentheses Python Solution

#python #stacks #datastructures

The problem statement is as follows:
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.

If you want to checkout the original problem go here

So first thing you would want to know is what the different parts of a parentheses is

opening = "{[("
closing = "}])"

we are also going to need to know the corresponding opening and closing brackets so we can put use a dictionary.

brackets = {')': '(', '}': '{', ']': '['}

So now we can go through the actual input string and check. If the character is an opening bracket, then we can push it onto a stack.
If it is a closing, we must check if our stack is empty or not. If it is empty, then we can return False.
Otherwise, we check the most recent item we pushed onto the stack and compare it with our current item. If they are matching open and close brackets then we can pop.

for char in s:
    if char in opening:
        stack.append(char)
    elif char in closing:
        if len(stack) == 0:
            return False
        if stack[-1] == brackets[char]:
            stack.pop()
        else:
            return False
return len(stack) == 0

full solution

def isValid(s):
    opening = "{[("
    closing = "}])"
    brackets = {')': '(', '}': '{', ']': '['}
    stack = []

    for char in s:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if len(stack) == 0:
                return False
            if stack[-1] == brackets[char]:
                stack.pop()
            else:
                return False
    return len(stack) == 0

Top comments (2)

Erfan Ansari • Jul 24 '21

in javascript:

var isValid = function(s) {
  const input = s.split('');
  const opening = ['(', '{', '['];
  const closing = [')', '}', ']'];

  const result = [];

  for (let i = 0; i < input.length; i++) {
    if (opening.includes(input[i])) {
      result.push(input[i]);
    } else if (closing.includes(input[i])) {
      const pos = closing.indexOf(input[i]);
      if (result.length === 0 || result[result.length - 1] !== opening[pos]) {
        return false;
      } else {
        result.pop();
      }
    }
  }
  return result.length === 0;
};