LeetCode #20: Valid Parentheses

LeetCode Solutions

https://leetcode.com/problems/valid-parentheses/

To solve this problem in Python 3, we can use a stack data structure to keep track of the opening brackets encountered in the input string s.

Here are the steps to follow:

  1. Initialize an empty stack.
  2. Iterate through the characters in the input string s.
  3. If the current character is an opening bracket ('(', '{', or '['), push it onto the stack.
  4. If the current character is a closing bracket (')', '}', or ']'), check if the top of the stack contains the corresponding opening bracket. If the stack is empty or the top of the stack does not match the corresponding opening bracket, return False.
  5. If all characters in the input string have been processed and the stack is empty, return True. Otherwise, return False.

Here’s the Python 3 code that implements this approach:

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

In this code, we first initialize an empty stack. We then iterate through the characters in the input string s. If the current character is an opening bracket ('(', '{', or '['), we push it onto the stack. If the current character is a closing bracket (')', '}', or ']'), we check if the top of the stack contains the corresponding opening bracket. If the stack is empty or the top of the stack does not match the corresponding opening bracket, we return False. If all characters in the input string have been processed and the stack is empty, we return True. Otherwise, we return False.

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the input string s.

The reason for this is that we iterate through the characters in s once using a for loop.

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the length of the input string s.

The reason for this is that we use a stack data structure to keep track of the opening brackets encountered in s. The size of the stack can be up to the length of s.