LeetCode Note Java 00020：Valid Parentheses

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 296 所需閱讀時間 ≈ 1 分鐘

判斷是否合法使用括號。

題目

Valid Parentheses Easy

Given a string s 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.
Every close bracket has a corresponding open bracket of the same type.

我的解法

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
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;
        }
        ArrayList<Character> stack = new ArrayList<>();
        for (char i : s.toCharArray()) {
            int lastIndex = stack.size() - 1;
            switch (i) {
                case ')':
                    if (!stack.isEmpty() && stack.get(lastIndex) == '(') {
                        stack.remove(lastIndex);
                    } else {
                        return false;
                    }
                    break;
                case '}':
                    if (!stack.isEmpty() && stack.get(lastIndex) == '{') {
                        stack.remove(lastIndex);
                    } else {
                        return false;
                    }
                    break;
                case ']':
                    if (!stack.isEmpty() && stack.get(lastIndex) == '[') {
                        stack.remove(lastIndex);
                    } else {
                        return false;
                    }
                    break;
                default:
                    stack.add(i);
            }
        }
        return stack.isEmpty();
    }
}

檢討

看了別人的解法才知道 Java 有 Stack 這個類能直接用。

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
class Solution {
    public boolean isValid(String s) {
        // Create hashmap to store the pairs...
        HashMap<Character, Character> Hmap = new HashMap<Character, Character>();
        Hmap.put(')','(');
        Hmap.put('}','{');
        Hmap.put(']','[');
        // Create stack data structure...
        Stack<Character> stack = new Stack<Character>();
        // Traverse each charater in input string...
        for (int idx = 0; idx < s.length(); idx++){
            // If open parentheses are present, push it to stack...
            if (s.charAt(idx) == '(' || s.charAt(idx) == '{' || s.charAt(idx) == '[') {
                stack.push(s.charAt(idx));
                continue;
            }
            // If the character is closing parentheses, check that the same type opening parentheses is being pushed to the stack or not...
            // If not, we need to return false...
            if (stack.size() == 0 || Hmap.get(s.charAt(idx)) != stack.pop()) {
                return false;
            }
        }
        // If the stack is empty, return true...
        if (stack.size() == 0) {
            return true;
        }
        return false;
    }
}

參考資料

Very Easy || 100% || Fully Explained (C++, Java, Python, JS, Python3)