java - 检查嵌套在字符串中的括号

Question

我参加了一个关于 Codility 的训练挑战，检查字符串中括号的嵌套是否正确。要检查的括号是{,},(,),[,]。我写了下面的 java 程序，它在 O(n) 的时间和空间中传递，但我有一种感觉，我使用的额外空间可以减少。另外我认为必须有一种数据结构可以更有效地处理这种情况。使用 ArrayList 而不是数组可能会有所帮助。我在这里需要的是对我的代码的批评。提前致谢。

这是我写的代码:

import java.util.HashMap;
class Solution {
    public int solution(String S) {
        char[] stack = new char[S.length()];
        int last = -1;
        HashMap hm = new HashMap();
        hm.put('}', '{');
        hm.put(')', '(');
        hm.put(']', '[');
        for(int i=0; i<S.length(); i++){
            char next = S.charAt(i);
            if(next == '}' || next == '{' || next == ')' || next == '(' ||
            next == ']' || next == '[')
            {
                if(last!=-1 && hm.containsKey(next) && stack[last] == hm.get(next)){
                    last--;
                }
                else{
                    last++;
                    stack[last] = S.charAt(i);
                }
            }
        }
        if(last == -1){
            return 1;
        }
        return 0;
    }
}

Answer 1

这是一个带有列表的解决方案:

import java.util.LinkedList;    

class Solution {

    public int solution(String S) {
        LinkedList<Character> stack = new LinkedList<>();

        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);

            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return 0;
                }

                char preceding = stack.pop();

                if (c == ')' && preceding != '(') {
                    return 0;
                }

                if (c == ']' && preceding != '[') {
                    return 0;
                }

                if (c == '}' && preceding != '{') {
                    return 0;
                }

            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}