20. Valid Parentheses

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

The brackets must close in the correct order,"()"and"()[]{}"are all valid but"(]"and"([)]"are not.

Thoughts:

Use the map to map each parentheses corresponding, Use a stack (either implemented as vector or stack) to keep track of current parentheses state.

class Solution {
public:
    bool isValid(string s) {
       unordered_map<char, char> map;
       vector <char> stack;
       map['(']  = ')';      
       map['[']  = ']';      
       map['{']  = '}';     
       for(auto i = s.begin(); i != s.end(); ++i){
           if(map.find(*i) != map.end()){
               stack.push_back(map[*i]);
           }
           else if (stack.empty() || stack.back() != (*i)){
                   return false;
           }
           else{
               stack.pop_back();
           }
       }
           return stack.empty();
    }
};

Python

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        d= {
            '(' : ')',
            '[' : ']',
            '{' : '}'
        }
        stack = []
        for c in s:
            if c in d:
                stack.append(d[c])
            elif stack and stack[-1] == c:
                stack.pop()
            else:
                return False

        return not stack