20. Valid Parentheses — LeetCode(Python)

I got you!

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.
2. 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

Constraints:

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

Solution:

if len(s) % 2 == 1: return False
bracket_map = {'(':')', '{':'}', '[':']'}
stack = []
for c in s:
    if c in bracket_map:
        stack += [c]
    elif not stack or bracket_map[stack.pop()] != c:
        return False
            
return stack == []

Explanation —

We use a stack to solve this problem.

First, we store all open-close parentheses as key-value pairs in a dictionary.

Next, we iterate through the string.

• If we come across an open parentheses, we push it to our stack.
• If, however, we come across a close parentheses, we check for two things — if the stack is empty, or if the top of the stack (which we pop) doesn’t match with our current character; we return False if either of these conditions is True.
• Finally, if our while loop terminates and we have processed the entire string, we return True if the stack is empty and False otherwise.

Time and Space Complexity —

Since we are iterating over all characters only once, we can say that our algorithm requires a linear amount of time to run.

Also, since we are using a stack, in the worst case, we might have to store all characters present in the string, we need a linear amount of space to run our code.

Thus, if n is the number of characters present in the string s,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏