Valid Parentheses

StackString

15 min

Problem Statement

Given a string s containing just the characters '(', ')', '</code>, <code className="bg-gray-700 px-2 py-1 rounded text-green-400">', '[' 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

Example 1:

Input: s = "()[]"

Input String:

()[]{}

Is Valid?

true

Output: true

Solution

A stack is the perfect data structure for this problem. When we encounter an opening bracket, we push it onto the stack. When we see a closing bracket, we check if the top of the stack is the corresponding opening bracket.

Algorithm Steps

Initialize an empty stack.
Create a map to store the matching pairs of brackets.
Iterate through the input string.
If the character is an opening bracket, push it onto the stack.
If it's a closing bracket, check if the stack is empty or if the top of the stack is not the matching opening bracket. If either is true, the string is invalid.
After the loop, if the stack is empty, the string is valid. Otherwise, it's invalid.

Input:()[]{}

Stack:

Start with an empty stack.

Valid Parentheses Solution


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