'lintcode 有效的括号序列'

Posted on | In

描述

给定一个字符串所表示的括号序列，包含以下字符： ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’， 判定是否是有效的括号序列。

括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]” 则是无效的括号。

样例

样例 1：

输入：”([)]”
输出：False
样例 2：

输入：”()[]{}”
输出：True

挑战

O(n)的时间，n 为括号的个数。

思路

遍历字符串，对于每个字符，如果是 ( { [ 就入栈，否则就和栈顶的对比，如果不配对就无效。
遍历完成之后栈中应当无字符，所以返回st.size() == 0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    bool isValidParentheses(string &s) {
        // write your code here
        if (s.length() == 0) return true;
        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                st.push(s[i]);
            else {
                if (st.size() == 0)
                    return false;
                char temp = st.top();
                if (
                    (s[i] == ')' && temp != '(') ||
                    (s[i] == ']' && temp != '[') ||
                    (s[i] == '}' && temp != '{')
                                                ) {
                    return false;
                }
                st.pop();
            }
        }
        return st.size() == 0;
    }
};
-------------end of filethanks for reading-------------