Valid Parentheses

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

http://www.lintcode.com/en/problem/valid-parentheses/

Discussion

比较简单。碰到左括号入栈，碰到右括号出栈，看出栈的左括号和碰到的右括号是否配对。最后栈应该是空的。

Solution

class Solution {
public:
    /**
     * @param s A string
     * @return whether the string is a valid parentheses
     */
    bool isValidParentheses(string& s) {
        // Write your code here
        int n = s.length();
        if(n==0) return true;
        stack<char> stk;
        for(int i=0; i<n; i++) {
            if (s[i]=='(' || s[i]=='[' || s[i]=='{') {
                stk.push(s[i]);
            } else {
                if(stk.empty()) {
                    return false;
                } else {
                    if(s[i] == mirror(stk.top())) {
                        stk.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        return stk.empty()==true;
    }
private:
    char mirror(char c) {
        if(c == '(')
            return ')';
        if(c == '[')
            return ']';
        if(c == '{')
            return '}';
    }
};

The same idea. By hash map plus a stack.

class Solution {
public:
    /**
     * @param s A string
     * @return whether the string is a valid parentheses
     */
    bool isValidParentheses(string& s) {
        // Write your code here
        unordered_map<char, char> map = {
            {'(',')'},
            {'[',']'},
            {'{','}'}
        };
        int n = s.length();
        stack<char> stk;
        for(int i=0; i<n; i++) {
            if(map.find(s[i]) != map.end()) {
                stk.push(s[i]);
            } else {
                if(stk.empty() == true) {
                    return false;
                } else if(s[i] !=  map[stk.top()]) {
                    return false;
                } else {
                    stk.pop();
                }
            }
        }
        return stk.empty()==true;
    }
};