Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0020 - Valid Parentheses
    0020 - Valid Parentheses
    0020 - Valid Parentheses
    0020 - Valid Parentheses

    0020 - Valid Parentheses

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/valid-parentheses/

    Solution 1 - Stack

    Use a stack to track opening brackets. For each closing bracket, check if it matches the most recent opening bracket on the stack. If the stack is empty at the end, the string is valid.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Stack using enumerate()

    Same stack-based approach, but uses enumerate() to also track character indices for potential debugging or extended use cases.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0020.1 - Valid Parentheses - Solution 1 - Stack """

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


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

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

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

        return not stack


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


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

    """ 0020.2 - Valid Parentheses - Solution 2 - Stack using Enumerate """

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


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

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

        for idx, char in enumerate(s):
            if char in open_brackets:
                stack.append(char)
            elif char in close_to_open:
                if not stack or stack[-1] != close_to_open[char]:
                    return False
                stack.pop()

        return len(stack) == 0


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


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