如何检查String中是否包含紧密组括号

Question

如何检查字符串以进行正确的分组.例如,以下组正确完成:

({})
[[]()]
[{()}]

接下来做错了:

{(})
([]
[])

正确的字符串不能以错误的顺序关闭组,打开组但无法关闭它,或者在打开组之前关闭组.

输入字符串,可以包含任何符号"()""{}"或"[]"来创建组.True如果字符串为空或以其他方式正确分组,或者False如果分组不正确,则返回输出.

愿任何人给我一些暗示.

Answer 1

主要思想是使用a Stack来跟踪预期的下一个相应括号.以下代码将起作用:

public boolean isValid(String s) {
    HashMap<Character, Character> closeBracketMap = new HashMap<Character, Character>();
    closeBracketMap.put(')', '(');
    closeBracketMap.put(']', '[');
    closeBracketMap.put('}', '{');
    HashSet<Character> openBracketSet = new HashSet<Character>(
        closeBracketMap.values());
    Stack<Character> stack = new Stack<Character>();

    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        char cur = chars[i];
        if (openBracketSet.contains(cur)) {
            stack.push(cur);
        } else { // close brackets
            if (stack.isEmpty()) {
                return false;
            }
            if (closeBracketMap.get(cur) != stack.peek()) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.isEmpty();
}