Problem :

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.

Example 1 :

**Input: s = "()"
Output: true**

Example 2 :

**Input: s = "()[]{}"
Output: true**

Example 3 :

**Input: s = "(]"
Output: false**

Example 4 :

**Input: s = "([])"
Output: true**

核心思維 :

1. 定義堆疊以儲存括號

2. 遍歷字串中的字符

   • 若當前字符是左括號，將其放入堆疊中
   • 若滿足
     1.字符是右括號
     2.堆疊不為空
     3.堆疊頂端的左括號能夠對應右括號，則將堆疊頂端的元素移出
   • 若沒有對應的括號則回傳false

3. 所有括號都配對完成，堆疊內應為空，否則回傳false

程式碼 :

class Solution {
public:
    bool isValid(string s) {
        //定義堆疊來儲存括號
        std::stack<int> mystack;
        //遍歷字串中的字符
        for(char c: s){
            //若當前字符是左括號，則放入堆疊中
            if(c == '(' || c == '{' || c == '['){
                mystack.push(c);
            //若滿足當前字符是右括號，堆疊不為空，並且堆疊頂端的左括號能夠對應右括號，則將堆疊頂端的元素移出
            }else if(c == ')' && !mystack.empty() && mystack.top() == '('){
                mystack.pop();
            }else if(c == '}' && !mystack.empty() && mystack.top() == '{'){
                mystack.pop();
            }else if(c == ']' && !mystack.empty() && mystack.top() == '['){
                mystack.pop();
            }else{
                //若沒有對應的括號，回傳false
                return false;
            }
        }
        //當所有括號都配對完成，堆疊內為空，否則回傳false
        return mystack.empty();
    }
};

結論 :

這題的目標是將括號放入堆疊中，並且檢查是否匹配，其中透過字符是左括號、右括號及是否有對應的括號來做判斷並進行字符的配對，其中活用堆疊操作簡單的特性，透過設立條件的方式進行配對，可以快速辨別此字串是否符合條件，善用堆疊的特性可以達成簡單明瞭且較短的執行時間的效益。