昨天我們講到Stack的基本操作，那今天來實際應用一次

20. Valid Parentheses

題目 20. Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

翻譯

給定一個字串 s，其中只包含字元 '('、')'、'{'、'}'、'[' 和 ']'，請判斷該輸入字串是否有效。

一個有效的字串必須符合以下條件：

1. 左括號必須由相同類型的右括號閉合
2. 左括號必須依照正確的順序閉合
3. 每個右括號都必須有一個相同類型的左括號與之對應

例如 :

() : 有效
()[]{} : 有效
(] : 無效(左右括號種類不同)
([)]: 無效(種類看似都有,但順序錯了)
{[]} : 有效(巢狀包起來也算對)

為什麼 "([)]" 是無效的?

• 掃到 (,
• 掃到 [,此時手上有兩個「還沒配對」的左括號 :( 和 [
• 掃到 ),這個右括號應該要跟誰配對?

應該要跟「離它最近的」那個左括號配對——也就是 [,而不是更早之前出現的 (。但 ) 對應的左括號應該是 (,不是 [,種類不符,所以判定無效。

流程

1. 建立一個空堆疊
2. 從頭掃描字串,一個字元一個字元處理:
   • 如果是左括號((、{、[),直接 push 進堆疊
   • 如果是右括號()、}、]):
     • 先檢查堆疊是不是空的，如果是空的,代表沒有左括號可以配對,直接判定無效
     • 再檢查堆疊頂端的左括號,跟目前這個右括號的種類是否對應 不對應就判定無效
     • 如果對應，把堆疊頂端的左括號 pop 掉(配對完成)
3. 掃描完整個字串後，還要檢查堆疊是不是空的
   如果還有剩下沒被配對的左括號(例如 "(((" 這種情況),也要判定無效,只有堆疊完全清空,才是真正的有效

程式碼

class Solution {
public:
    bool isValid(string s) {
        stack<char> c;   // 用來存放「還沒被配對」的左括號
 
        for (int i = 0; i < s.length(); i++) {
 
            // 情況一:遇到左括號,直接push進堆疊,先記住它
            if (s[i]=='('||s[i]=='{'||s[i]=='[') {
                c.push(s[i]);
 
            } else {
                // 情況二:遇到右括號,要先確認有沒有左括號可以配對
 
                if (c.empty()) {
                    // 堆疊是空的,代表沒有任何左括號可以配對,直接判定無效
                    return false;
                }
 
                // 分別檢查三種右括號,是否對應堆疊頂端(最近)的左括號
                if (s[i]==')' && c.top()!='(') {
                    return false;   
                } else if (s[i]==']' && c.top()!='[') {
                    return false;   
                } else if (s[i]=='}' && c.top()!='{') {
                    return false;   
                } else {
                    // 種類相符,配對成功,把這個左括號從堆疊移除
                    c.pop();
                }
            }
        }
 
        // 整個字串掃描完之後,檢查堆疊是否清空
        if (c.empty()) {
            return true;    // 清空了,代表所有括號都正確配對
        } else {
            return false;   // 還有剩,代表有左括號沒被配對到
        }
    }
};

用兩個例子來看
"([)]"(無效):

"{[]}"(有效):

複雜度分析

• 時間複雜度:O(n) — 字串只需要掃過一次

那接下來,我們會進到佇列(Queue)的介紹,看看跟堆疊 LIFO 相反的 FIFO 特性,適合用在什麼場景。