0020 - Valid Parentheses

Difficulty

Easy

Language

Python

URL

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

Solution 1 - Stack with Mapped Closing Brackets

For each character in the string, if it's an opening bracket, push the corresponding closing bracket onto the stack. If it's a closing bracket, check if the stack is non-empty and the top matches the current character. If not, return False. At the end, the string is valid only if the stack is empty.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0020.1 - Valid Parentheses - Solution 1 - Stack with Mapped Closing Brackets """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isValid(self, s: str) -> bool:
        """Valid Parentheses Function"""
        stack = []

        for c in s:
            if c == '(':
                stack.append(')')
            elif c == '{':
                stack.append('}')
            elif c == '[':
                stack.append(']')
            elif not stack or stack.pop() != c:
                return False

        return not stack


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isValid("()"))         # True
    print(Solution().isValid("()[]{}"))     # True
    print(Solution().isValid("(]"))         # False
    print(Solution().isValid("([])"))       # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Stack with Dictionary Lookup

Use a dictionary to map each closing bracket to its corresponding opening bracket. For each character, if it's a closing bracket, pop the top of the stack and check if it matches the expected opening bracket. If it's an opening bracket, push it onto the stack.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0020.2 - Valid Parentheses - Solution 2 - Stack with Dictionary Lookup """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isValid(self, s: str) -> bool:
        """Valid Parentheses Function"""
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}

        for c in s:
            if c in mapping:
                top = stack.pop() if stack else '#'
                if mapping[c] != top:
                    return False
            else:
                stack.append(c)

        return not stack


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isValid("()"))         # True
    print(Solution().isValid("()[]{}"))     # True
    print(Solution().isValid("(]"))         # False
    print(Solution().isValid("([])"))       # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()