# 【LeetCode】 20. Valid Parentheses

## Description
> 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.

> 給一字串只包含 '(', ')', '{', '}', '[' and ']' 這些字元，請判斷該字串是否合法。
> 一個合法字串應該：
> - 相同類型的左右括號一組 //我不知道怎麼翻譯XD
> - 括號裡面也是正確的括號 //同上
> 注意，空字串也是合法的字串。

## Example:

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

## Solution

* 用一個stack紀錄上一個左括號種類。
* 遇到右括號就去判斷和stack pop出來的是不是同一種的。
* 整個字串跑完，如果stack是空的，即為合法字串。

### Code

class Solution {
public:
    bool isAnother(char a,char b)
    {
        return ((a=='('&&b==')') || (a=='['&&b==']') || (a=='{'&&b=='}'));
    }
    
    bool isValid(string s) {
        vector<char> v;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='[' || s[i]=='(' || s[i]=='{')
            {
                v.push_back(s[i]);
            }
            else 
            {
                if(!v.empty() && isAnother(v.back(),s[i]))
                    v.pop_back();
                else
                    return false;
            }
        }
        return v.empty();
    }
};

###### tags: `LeetCode` `C++`