【LeetCode】#20 Valid Parentheses 詳細完整解法

Valid Parentheses

題目描述

給你一組字串 s ,字串中只會出現「(、)、{、}、[、]」這些括號,去判斷字串是否符合通過條件。

字串的通過條件:

  1. 所有的開口括弧都必須被關上,而且要使用成對的括弧,「()、{}、[]」。
  2. 括弧必須按照正確的順序才能算關上。

限制條件

  • 字串長度在 1 ~ 10^4 之間。
  • 字串 s 只會由「( )[ ]{ }」組成。

解題思路

這一題是配對消除遊戲,通過條件需要成對的消除括弧,這個應該很容易理解。

而通過條件2的正確順序,指的是成對的括弧中間不能夠有其他類型的括弧阻擋。舉例來說:

():這是一個關閉的括弧。

([):這是一個被阻擋的括弧。

當出現被阻擋的狀況,表示括弧無法被關上,所以字串是不合格的。

那我們要怎麼完成這一題呢?

先來理解狀況,每當遇到一個左括弧的時候,下一個位置不一定會出現成對的右括弧,如果是不成對的右括弧,我們就可以直接判定是字串不合格,但是還有一種情況是,繼續出現左括弧。所以情況可能會變成這樣,

{[(:重複出現左括弧。

很顯然的,在這邊我們必須要設計將每個出現的左括弧儲存起來,等到出現右括弧之後,再把存起來的左括弧拿出來配對看可不可以消除。

堆疊 Stack

按照上面的思路,儲存的需求剛好會符合一種資料結構「堆疊(Stack)」,Stack的特性是先進後出(First In Last Out, FILO),或者也可以說成LIFO,我們想要處裡的括號們也是先配對後面進來的括號,再處理之前存入的括號。

Stack的應用也是這一題想要讓我們學習的技術核心。

程式碼

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;                                 //宣告stack容器,用來存入左括號。
        for(int i=0;i<s.length();i++){                  //開始從頭查詢整組字串。
            if(s[i]=='(' or s[i]== '{' or s[i]== '['){  //如果發現左括號,存入stack。
                st.push(s[i]);                
            }else{                                      //如果不是左括號,就是右括號。
                if(st.empty()) return false;            //當出現右括號,但是沒左括號配對,就回傳false。
                if(st.top()=='(' and s[i]==')'){        //配對括號,如果配對成功,將左括號從stack中移除。
                    st.pop();
                }else if(st.top()=='{' and s[i]=='}'){
                    st.pop();
                }else if(st.top()=='[' and s[i]==']'){
                    st.pop();
                }else{
                    return false;
                }
            }            
        }
        if(st.empty()) return true;                      //整組字串檢查完後,stack沒有殘留任何左括號代表成功通過判定。
        else return false;                               //反之,則是失敗,回傳false。
    }
};

時間複雜度分析

一組字串從頭跑到尾,只用了一個for迴圈,時間複雜度為O(n)。

空間複雜度分析

使用了一個容器stack,最壞的情況下,字串內全部都是左括號,空間複雜度會是O(n)。

延伸閱讀

FIFO、FILO、LILO、LIFO有什麼不一樣?與容器之間是什麼關係?

在〈【LeetCode】#20 Valid Parentheses 詳細完整解法〉中有 1 則留言

  1. 自動引用通知: 【LeetCode】 刷題地圖 - 人生自習室

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

回到頂端