Logo for ammarahmed.ca
Easy
May 27, 2025
#stack

20. Valid Parentheses

Problem

Given a string s 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.
    1. Open brackets must be closed in the correct order.
      1. Every close bracket has a corresponding open bracket of the same type.

        Example 1:

        Input: s = "()"

        Output: true

        Example 2:

        Input: s = "()[]{}"

        Output: true

        Example 3:

        Input: s = "(]"

        Output: false

        Example 4:

        Input: s = "([])"

        Output: true

        Constraints:

        • 1 <= s.length <= 104
          • s consists of parentheses only '()[]{}'.

            Approach

            We can use a stack to solve this problem.

            We iterate through the string, whenever we see an opening bracket, we push the corresponding closing bracket to the stack. When we see a closing bracket, we check if the top of the stack is the same bracket, if it's not, we can return false early. Otherwise, we pop from the stack and continue iterating. If we reach the end and the stack is empty, the parentheses are valid. If the stack is not empty, that means something was not closed and we can return false.

            Complexity

            Time: O(n)

            We iterate over the input once.

            Space: O(n)

            We create a stack that can possibly contain all the elements of the input.

            Solution

            1func isValid(s string) bool { 2 p := map[rune]rune{ 3 '{': '}', 4 '[': ']', 5 '(': ')', 6 } 7 var stack []rune 8 for _, c := range s { 9 closing, isOpening := p[c] 10 if isOpening { 11 stack = append(stack, closing) 12 } else { 13 if len(stack) == 0 { 14 return false 15 } 16 top := stack[len(stack) - 1] 17 if top != c { 18 return false 19 } 20 stack = stack[:len(stack) - 1] 21 } 22 } 23 24 return len(stack) == 0 25}