Leetcode 20. Valid Parentheses

給定一個字符串，只包含'(', ')', '{', '}','['和 ']' 這幾個字符，判斷輸入字符串是否是有效的。

輸入字符串在以下情況下有效：

開括號必須用相同類型的括號閉合。
開括號必須以正確的順序閉合。
每個右括號都有一個對應的相同類型的左括號。

Python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {']':'[', ')':'(', '}':'{'}
        for c in s:
            if c not in dic:             #字符不在dic字典，左括號
                stack.append(c)       
            else:                        #字符在dic字典，右括號
               if not stack or stack.pop() != dic[c]: #為空或括號不對應
                    return False
        return stack == []               #stack是否為空

這題是使用 stack特性解題。只要碰到 (、{、[ 就將其放入 stack 中，如果遇到 )、}、] 則匹配 stack 的最頂部（stack 是後進先出的資料結構），如果是合法的匹配，則將其 stack 頂部的字符彈出。如果 stack 為空，而又碰到了需要匹配 )、}、] 的情況，則意味著這是個不合法的字串，直接回傳 false。如果匹配到最後 stack 為空，回傳 true、反之則 false。

class Solution:
    def isValid(self, s: str) -> bool:
        # Init
        stack = []
        
        # Matching
        for c in s:
            if c in ['(', '{', '[']:
                stack.append(c)
            elif len(stack) == 0: return False
            elif stack[-1] == '(' and c != ')': return False
            elif stack[-1] == '{' and c != '}': return False
            elif stack[-1] == '[' and c != ']': return False
            else: stack.pop()
        
        return len(stack) == 0

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> st; 
        for(char i: s){

        //如果是左括號或堆疊為空，加入堆疊
            if (st.empty() || i == '(' || i == '[' || i == '{'){
                st.push(i);  
            }

        //如果是右括號，比對是否有對應左括號，如果有pop左括號出來
            else if (i == ')' && st.top() == '(' || i == ']' && st.top() == '[' || 
                    i == '}' && st.top() == '{'){
                st.pop();  

            }
            else{
                return false; //如果都沒有，回傳false
            }   
        }
        return st.empty();  //最後如果stack為空回傳true
    }
};

Python

C++

相關