Devin's Blog

Valid Parantheses

2 min read

Time: 17:04

Neetcode not as Good in Speed, but much Better Memory

class Solution:
    def isValid(self, s: str) -> bool:
        Map = {")": "(", "]": "[", "}": "{"}
        stack = []
 
        for c in s:
            if c not in Map:
                stack.append(c)
                continue
            if not stack or stack[-1] != Map[c]:
                return False
            stack.pop()
 
        return not stack

Just Stack

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in range(len(s)):
            if s[i] == '(':
                stack.append('(')
            elif s[i] == '{':
                stack.append('{')
            elif s[i] == '[':
                stack.append('[')
            elif stack == []:
                return False
            elif s[i] == ')':
                if stack.pop() != '(':
                    return False
            elif s[i] == '}':
                if stack.pop() != '{':
                    return False
            elif s[i] == ']':
                if stack.pop() != '[':
                    return False
        
        return stack == []

Stack + counter

class Solution:
    def isValid(self, s: str) -> bool:
        open_parantheses_count = 0
        open_curly_count = 0
        open_bracket_count = 0
 
        stack = []
        for i in range(len(s)):
            if s[i] == '(':
                open_parantheses_count += 1
                stack.append('(')
            elif s[i] == '{':
                open_curly_count += 1
                stack.append('{')
            elif s[i] == '[':
                open_bracket_count += 1
                stack.append('[')
            elif s[i] == ')':
                if open_parantheses_count == 0:
                    return False
                if stack.pop() != '(':
                    return False
 
                open_parantheses_count -= 1
            elif s[i] == '}':
                if open_curly_count == 0:
                    return False
                if stack.pop() != '{':
                    return False
                open_curly_count -= 1
            elif s[i] == ']':
                if open_bracket_count == 0:
                    return False
                if stack.pop() != '[':
                    return False
                open_bracket_count -= 1
        
        if open_parantheses_count != 0:
            return False
        if open_curly_count != 0:
            return False
        if open_bracket_count != 0:
            return False 
 
        return True

References

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

Graph View