LeetCode20. Valid Parentheses（模拟）

LeetCode20. Valid Parentheses（模拟）

• Easy
• Accepted：631,556
• Submissions：1,715,760

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

链接

https://leetcode.com/problems/valid-parentheses/

题意

判断一个括号串在指定规则下是否合法。

题解

使用栈模拟即可。

代码

• Runtime: 0 ms, faster than 100.00% of C++ online submissions for Valid Parentheses.
• Memory Usage: 8.6 MB, less than 22.61% of C++ online submissions for Valid Parentheses.

class Solution {
public:
    bool isValid(string s) {
        int n = s.length();
        stack <char> st;
        while (!st.empty())
            st.pop();
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[')
                    st.push(s[i]);
            else if (!st.empty() && st.top() == '(' && s[i] == ')')
                st.pop();
            else if (!st.empty() && st.top() == '[' && s[i] == ']')
                st.pop();
            else if (!st.empty() && st.top() == '{' && s[i] == '}')
                st.pop();
            else
                return false;
        }
        return st.empty();
    }
};

还有一种更牛逼的解法，JAVA版本。

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}

但是在C++中好像并不能将stack.pop()作为变量使用，不过更重要的是这种思维。

The end.
2019年7月14日 星期日