作者 Ivan Chien
始于 
分类：LeetCode
Tags: [ LeetCode ]
LeetCode 百题计划 - 20. Valid Parentheses

LeetCode 20. Valid Parentheses

20. Valid Parentheses

Difficulty: easy

Given a string 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.
  2. 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

Only Version:

class Solution {
public:
    int cToN(const char c) {
        switch (c) {
            case '(': return 0;
            case '[': return 1;
            case '{': return 2;
            case '}': return 3;
            case ']': return 4;
            case ')': return 5;
            default: assert(0);
        }
        return 6;
    }
    
    bool isValid(string s) {
        vector<char> stk;
        if (s.size() % 2)
            return false;
        auto itr = begin(s);
        while (itr != end(s)) {
            if (cToN(*itr) > 2) {
                if (stk.empty() or cToN(*itr) + cToN(stk.back()) != 5) {
                    return false;
                }
                else {
                    stk.pop_back();
                }
            } else {
                stk.push_back(*itr);
            }
            ++itr;
        }
        
        if (stk.empty()) {
            return true;
        } else {
            return false;
        }
    }
};

Rate:
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Valid Parentheses.
Memory Usage: 8.5 MB, less than 83.72% of C++ online submissions for Valid Parentheses.

满满我自己风格的代码, switch封装函数.
题目是非常简单的, 因为之前在HDOJ上做过类似的Train Problem I, 当时就想到是用栈写的, 所以这次这个题目也变得非常容易.