Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    0020 - Valid Parentheses
    0020 - Valid Parentheses

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: 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()

    """ 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()