題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個字串 s

這個字串只會由 6種符號 組成，分別是 ( ) { } [ ]

必須驗證傳入的字串 s 中的符號是不是有被正確匹配

範例:

s = "()"，則回傳 true
s = "()[]{}"，則回傳 true
s = "(]"，則回傳 false

解題思路

一開始我的第一直覺是利用前後索引來驗證，但遇到以下狀況就會驗證失敗

"[(){}]"，這個情況是要回傳 true 的，因為所有的符號都有正確匹配

所以正確的思路是利用一個 堆(Stack) 來解題

堆的特色就是「後進先出」，這剛好完美地應對這一題

所謂的「後進先出」就是最後放入的東西會先被丟出來

利用一個迴圈掃過一次字串 s ，如果遇到開頭符號 ( { [

我們就把結束符號放入 Stack 中，如果遇到結束符號 ) } ]

就把 Stack 中的最後一個元素丟出，如果不一樣或 Stack 已空就回傳 false

最後再檢查一下 Stack 是不是空的就行了

程式碼

Java

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack(); 
        // 除了用 Stack 以外也能用 List 或是 Array 達到一樣的效果，只是沒有用 Stack 來的簡潔
        
        for (char c: s.toCharArray()) {
            switch (c) {
                case '(':
                    stack.push(')');
                    continue;
                    
                case '[':
                    stack.push(']');
                    continue;
                    
                case '{':
                    stack.push('}');
                    continue;
                    
                default:
                    if (stack.empty() || (char)stack.pop() != c) {
                        return false;
                    }
                    
            }
        }
        
        return stack.empty(); // 可能會有多餘的符號在 Stack 中，所以最後需要再檢查一次
    }
}