--

leetcode 020: Valid Parentheses

https://leetcode.com/problems/valid-parentheses/

---

---

problem:

---

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true

---

---

start code (c++)

---

---

---

solution:

我的思路：
利用一个后进先出的 stack 来存储括号。

---

 
class Solution {
public:
    bool isValid(string s) {
        stack stk;
        for (int i = 0; i < s.size(); i ++){
            if (s[i] == '(' || s[i] == '[' || s[i] == '{'){
                stk.push(s[i]);
            }else if (s[i] == ')'){
                if (stk.size() == 0 || stk.top() != '(')
                    return false;
                stk.pop();
            }else if (s[i] == ']'){
                if (stk.size() == 0 || stk.top() != '[')
                    return false;
                stk.pop();
            }else if (s[i] == '}'){
                if (stk.size() == 0 || stk.top() != '{')
                    return false;
                stk.pop();
            }
        }
        return stk.size() == 0;
        
    }
};

---