###### tags: `Leetcode` `easy` `stack` `python` `c++` `Top 100 Liked Questions`

# 20. Valid Parentheses

## [題目來源:] https://leetcode.com/problems/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.
1. Open brackets must be closed in the correct order.
1. Every close bracket has a corresponding open bracket of the same type.

## 解題想法:
只存左刮號於stack
使用dict存pair種類 key為右括號、val為左刮號

## Python:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack=[s[0]] #只存open
        openDic=set(['(','[','{'])
        #key: close  value:open
        pair={')':'(', ']':'[', '}':'{'}
        for char in s[1:]:
            if char in openDic: #serach O(1)
                stack.append(char)
            else:
                if not stack:  #沒左刮
                    return False
                last=stack.pop()
                if pair[char]==last: #合法配對
                    continue
                else:
                    return False
        return True if not stack else False #左刮太多False

result=Solution()
ans=result.isValid(s = "()[]{}")
print(ans)

## C++:
可以使用 #include <bits/stdc++.h> 一行打天下

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    bool isValid(string s)
    {
        unordered_map<char, char> pair;
        pair = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        stack<char> myStack;
        myStack.push(s[0]);
        for (int i = 1; i < s.size(); i++)
        {
            if (pair.find(s[i]) == pair.end())
                myStack.push(s[i]);
            else
            {
                if (myStack.empty())
                    return false;
                char val = myStack.top();
                myStack.pop();
                if (pair[s[i]] == val)
                    continue;
                else
                    return false;
            }
        }
        if (myStack.empty())
            return true;
        else
            return false;
    }
};

int main()
{
    Solution res;
    string s = "()[]{}";
    bool ans = res.isValid(s);
    cout << ans << endl;
    return 0;
}