Valid Parentheses

发表于

算法分类：Stack

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

​

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
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

​

Java解法

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
31
32
33
34
35
36
37
38
class Solution {
    public boolean isValid(String s) {
        Stack<String> stack = new Stack<>();
        char[] chArr = s.toCharArray();
        for (char ch : chArr) {
            String top = stack.isEmpty() ? null : stack.peek();
            String c = String.valueOf(ch);
            if (null == top) {
                stack.push(c);
            } else if (top.equals("{")) {
                if (c.equals("}")) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else if (top.equals("[")) {
                if (c.equals("]")) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else if (top.equals("(")) {
                if (c.equals(")")) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else {
                stack.push(c);
            }
        }
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        HashMap<Character, Character> map = new HashMap<Character, Character>() {{
            put('}', '{');
            put(']', '[');
            put(')', '(');
        }};
        char[] chArr = s.toCharArray();
        for (char ch : chArr) {
            Character top = stack.isEmpty() ? null : stack.peek();
            if (null == top) {
                stack.push(ch);
            } else if (top == map.get(ch)) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

​

Python解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        map = {u'}':u'{', u']':u'[', u')':u'('}
        for ch in s:
            top = u'#' if (len(stack) == 0) else stack[-1]
            if map.has_key(ch) and top == map[ch]:
                stack.pop()
            else:
                stack.append(ch)

        return 0 == len(stack)