Valid Parentheses

We can solve this problem using a stack data structure. The idea is to push the opening brackets into the stack and pop them out when a matching closing bracket is found. If the string is valid, the stack should be empty at the end.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # Mapping of the brackets
        mapping = {')': '(', '}': '{', ']': '['}

        for char in s:
            # If the character is a closing bracket
            if char in mapping:
                # Pop the top element if stack is not empty, otherwise assign a dummy value
                top_element = stack.pop() if stack else '#'

                # Check if the popped element matches the current closing bracket
                if mapping[char] != top_element:
                    return False
            else:
                # Push the opening bracket to the stack
                stack.append(char)

        # If the stack is empty, the string is valid
        return not stack

Explanation:

  • If the current character is an opening bracket, it’s pushed onto the stack.
  • If it’s a closing bracket, the top element of the stack is popped, and we check if it matches the corresponding opening bracket.
  • If the stack is empty at the end of the iteration, the brackets are balanced, and the string is valid. If not, the string is invalid.

This solution takes linear time, as it scans through the string once, and constant extra space, as it uses a fixed-size mapping and a stack whose size is proportional to the length of the input string.

title: Valid Parentheses excerpt: This covers using stack to solve problems. tags: linear-scan stack

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.
Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints

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

Problem Definition

Define the Interface

Input: string Output: boolean

Identify Implicit Inputs

Possible brackets are: ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’

If you begin the string with closing parenthesis, it is false.

Search the Problem Space

Look for clues in the problem statement. In this case, the order of the brackets matter. So we need to think of using either queue or stack.

Brute Force Approach

  • Push the open parenthesis
  • Pop if the closing parenthesis matches
  • The stack is empty and we have scanned all characters in the string. We return true.
  • I have scanned all the characters in the string. The stack is not empty. We return false.
  • When we encounter a closing parenthesis, it must be a closing parenthesis for the type of parenthesis at the top of the stack. If it is not, return false immediately.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

def opening?(open)
  if open == '('
    return true
  end
  
  if open == '{'
    return true
  end    
  
  if open == '[' 
    return true
  end 
  
  return false
end

def matches?(open, close)
  if open == '(' && close == ')'
    return true
  end
  
  if open == '{' && close == '}'
    return true
  end    
  
  if open == '[' && close == ']'
    return true
  end    

  return false
end

# @param {String} s
# @return {Boolean}
def is_valid(s)
  stack = []
  n = s.size
  
  for i in (0...n)
    # if the current character is an opening parenthesis
    # push it and continue

    if opening?(s[i])
      stack << s[i]
      next
    end
    
    if stack.empty?
      return false
    end
    
    # Case 1: top of stack matches 
    # Case 2: top of stack does not match
      
    # if the current character is an closing parenthesis
    # and matches with the element on the top, we will pop
    # the element
    if matches?(stack[-1], s[i])
      stack.pop
    else
      return false
    end
  end
   
  stack.empty?
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

def opening?(open)
  open == '(' || open == '{' || open == '[' 
end

def matches?(open, close)
  smooth = open == '(' && close == ')'
  curly =  open == '{' && close == '}'
  square = open == '[' && close == ']'
    
  smooth || curly || square
end

# @param {String} s
# @return {Boolean}
def is_valid(s)
  stack = []
  n = s.size
  
  for i in (0...n)
    # if the current character is an opening parenthesis
    # push it and continue

    if opening?(s[i])
      stack << s[i]
      next
    end
    
    if stack.empty?
      return false
    end
    
    # Case 1: top of stack matches 
    # Case 2: top of stack does not match
      
    # if the current character is an closing parenthesis
    # and matches with the element on the top, we will pop
    # the element
    if matches?(stack[-1], s[i])
      stack.pop
    else
      return false
    end
  end
   
  stack.empty?
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def opening?(open)
  open == '(' || open == '{' || open == '[' 
end

# @param {String} s
# @return {Boolean}
def is_valid(s)
  hash = {')' => '(',  '}' => '{', ']' => '[' }
    
  stack = []
  n = s.size
  
  for i in (0...n)
    # if the current character is an opening parenthesis
    # push it and continue

    if opening?(s[i])
      stack << s[i]
      next
    end
    
    if stack.empty?
      return false
    end
    
    # Case 1: top of stack matches 
    # Case 2: top of stack does not match
      
    # if the current character is an closing parenthesis
    # and matches with the element on the top, we will pop
    # the element
    if hash[s[i]] == stack[-1]
      stack.pop
    else
      return false
    end
  end
   
  stack.empty?
end

Variant

A simpler version of the problem is there is only one type of bracket in the string and the code can be simplified.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

def valid?(s)
  stack = []
  n = s.size
  
  for i in (0..n-1)
    # if the current character is an opening parenthesis
    # push it and continue

    if s[i] == '('
      stack << s[i]
      next
    end
        
    # Case 1: top of stack matches 
    # Case 2: top of stack does not match
      
    # if the current character is an closing parenthesis
    # and matches with the element on the top, we will pop
    # the element
    if s[i] == ')'
      if stack.empty?
        return false
      else
        stack.pop
      end
    end
  end
   
  stack.empty?
end

input = "(coding)(skill)"
p valid?(input)

Building Block

  • Linear Scan
  • Stack

Identifying Problem Isomorphism

“Valid Parentheses” shares a close resemblance to “Balanced Brackets”.

In “Valid Parentheses”, you’re given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’. You have to determine if the input string is valid, with an input string being valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

“Balanced Brackets” presents a similar problem where you’re given a string of brackets and you have to decide whether the sequence of brackets is balanced. The rules of balanced brackets are:

  1. For every bracket that is opened, the same type of bracket must close it.
  2. The brackets must close in the correct order.

The concept of using a data structure like a stack to keep track of the opening brackets until we encounter a closing bracket can be applied to both problems, making them isomorphic problems. When a closing bracket is encountered, we check the top of the stack and if the opening bracket of the same type is there, we remove it, otherwise, the sequence is not balanced.

Both problems are of similar complexity as they involve the same logical steps. “Valid Parentheses” is simpler due to the lesser variety of bracket types in the input.

10 Prerequisite LeetCode Problems

“Valid Parentheses” (LeetCode 20) is a common introductory problem for understanding stacks, for simpler problems, consider the following:

  1. “344. Reverse String”: This problem is about reversing a string, and although it’s straightforward, it can help you understand strings and arrays in more depth.

  2. “1. Two Sum”: This is a classic introductory problem for understanding arrays and hashmaps.

  3. “13. Roman to Integer”: This problem asks you to convert a Roman numeral to an integer. It can help you get familiar with the concept of a lookup table, which is essentially a kind of hash map.

  4. “26. Remove Duplicates from Sorted Array”: This problem asks you to remove duplicates in-place in a sorted array. It can help you understand the concept of two pointers.

  5. “283. Move Zeroes”: This problem requires you to move all zeroes in an array to the end while maintaining the order of the other elements. It’s a good practice problem for in-place array manipulation.

  6. “35. Search Insert Position”: This problem is about binary search, which is a common technique for efficient searching in sorted arrays.

  7. “58. Length of Last Word”: This problem requires you to find the length of the last word in a string, helping to understand string manipulation concepts.

  8. “217. Contains Duplicate”: This problem asks you to determine if an array contains any duplicates, providing practice with array manipulation and set data structures.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for char in s:
            if char == '(' or char == '{' or char == '[':
                stack.append(char)
            else:
                if not stack:
                    return False
                if char == ')' and stack[-1] == '(':
                    stack.pop()
                elif char == '}' and stack[-1] == '{':
                    stack.pop()
                elif char == ']' and stack[-1] == '[':
                    stack.pop()
                else:
                    return False
        return not stack

Problem Classification

  1. String manipulation: The problem requires you to handle and process string inputs, specifically strings containing various types of brackets. Thus, a good understanding of strings and string operations is needed.

  2. Stack data structure: The problem uses the LIFO (Last In First Out) principle to check for balanced parentheses. This is a fundamental use case for the stack data structure.

  3. Parentheses/Brackets Matching: This is the specific problem domain - the task of checking if the open-close brackets in a given string are properly paired and nested.

The problem is a mix of string manipulation, data structure (specifically, stack), and parentheses matching.

Language Agnostic Coding Drills

  1. Understanding Stacks: The stack data structure follows the Last-In-First-Out (LIFO) principle, which is essential to understand the solution. A stack allows adding an item or “pushing” to the top of the stack, and removing an item or “popping” from the top of the stack.

  2. Understanding Parentheses Balance Concept: The problem is about validating if the given string has balanced parentheses. Balanced parentheses mean that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.

  3. Conditionals and Loops: The problem requires a knowledge of iterative constructs like for-loops and conditional constructs like if-else statements to traverse through the string and to perform operations based on certain conditions.

  4. String Manipulation: This involves understanding how to iterate over a string, access individual characters, and compare characters.

Problem Solving Approach:

  1. Initialization: Start by initializing an empty stack. The stack is used to keep track of the opening brackets.

  2. Iterating through the string: Loop over each character in the string. If the character is an opening bracket, push it onto the stack. If it’s a closing bracket, check the top element of the stack.

  3. Matching Brackets: If the top element in the stack is the corresponding opening bracket, pop it from the stack. If not, return False, as the string is not balanced.

  4. Stack Check after Iteration: After we’ve iterated through all the characters in the string, check if the stack is empty. If it’s empty, it means all opening brackets had their corresponding closing ones (the string was balanced), and we return True. If not, return False.

This general approach can be used in most modern programming languages. You’ll need to understand the language-specific syntax for implementing stacks and string manipulation, but the overall strategy remains the same.

Targeted Drills in Python

Drill 1: Understanding Stacks Here you need to learn how to create a stack, and how to use push and pop operations. The list data structure in Python can be used as a stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Creating a stack (which is basically a list)
stack = []

# Pushing an element onto the stack (appending to the end of the list)
stack.append('(')

# Popping an element off the stack (removing from the end of the list)
element = stack.pop()

print(element)  # This should print '('

Drill 2: Conditionals and Loops Understanding how to use conditional (if-else) statements and loops is vital for this problem.

1
2
3
4
5
6
7

s = "(())"

for char in s:
    if char == '(':
        print("This is an opening bracket")
    else:
        print("This is a closing bracket")

Drill 3: String Manipulation In this problem, you’re dealing with strings. You need to understand how to iterate through a string and how to compare characters.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

s = "(())"
# Iterating through a string
for char in s:
    print(char)
    
# Comparing characters
if s[0] == s[1]:
    print("The characters are the same")
else:
    print("The characters are different")

Drill 4: Understanding Parentheses Balance Concept Finally, you need to understand how to check for balanced parentheses. This is where you’ll put everything together.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def is_balanced(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return not stack

print(is_balanced("(())"))  # This should print True
print(is_balanced("(()))"))  # This should print False

Once you’ve worked through these drills and understand each of the concepts, you can then combine them to solve the problem in the final integrated drill, which would involve modifying the is_balanced function to handle all types of brackets, not just parentheses.