LC20. Valid Parentheses

Approach 1: Optimal

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        pairing = {
            ']': '[',
            ')': '(',
            '}': '{'
        }
 
        try:
            for c in s:
                if c in pairing:
                    popped = st.pop()
                    if popped != pairing[c]:
                        return False
                else:
                    st.append(c)
        except IndexError:
            return False
        
        if len(st) != 0:
            return False
 
        return True
 

Complexity

Time: $O(n)$
Space: $O(n)$

Other Languages

Go

func isValid(s string) bool {
    pairing := map[string]string {
        "]": "[",
        ")": "(",
        "}": "{",
    }
    var st []string
 
    for _, c := range s {
        if _, ok := pairing[string(c)]; ok {
            var popped string
            popped, st, ok = pop(st)
 
            if !ok {
                return false
            }
 
            if popped != pairing[string(c)] {
                return false
            }
        } else {
            st = append(st, string(c))
        }
    }
 
    if len(st) != 0 {
        return false
    }
 
    return true
}
 
func pop(slice []string) (string, []string, bool) {
    if len(slice) == 0 {
        return "", slice, false
    }
 
    popped := slice[len(slice) - 1]
    return popped, slice[:len(slice) - 1], true
}