[LeetCode] 20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

思路:先用flag 紀錄每個左符號出現的次數 再用stack紀錄 順序
掃一遍 s 並處理 順序和出現個數 不合格式的情況
最後如果 所有的 flag 都為0 表示字串一切合法.



class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        p, q, r = 0, 0 ,0
        st = []
        for i in s:
            if i == '(':
                p += 1
                st.append(i)
            if i == '{':
                q += 1
                st.append(i)
            if i == '[':
                r += 1
                st.append(i)
            if i == ')':
                if p > 0 and st[-1] == '(':
                    p -= 1
                    st.pop()
                else: return False
            if i == '}':
                if q > 0 and st[-1] == '{':
                    q -= 1
                    st.pop()
                else: return False
            if i == ']':
                if r > 0 and st[-1] == '[':
                    r -= 1
                    st.pop()
                else: return False

        return True if p == 0 and q == 0 and r == 0 else False