有效的括号

原题链接

使用的方法

栈

解题思路

• 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
• 我们可以使用栈来解决这个问题。栈是一种后进先出（LIFO）的数据结构，非常适合处理括号匹配的问题。
• 我们遍历字符串中的每个字符，如果遇到左括号，我们将其压入栈中；如果遇到右括号，我们检查栈顶元素是否是对应的左括号。
  • 如果是，我们将栈顶元素弹出；
  • 如果不是，或者栈为空，我们就可以确定字符串无效。
• 最后，如果栈为空，说明所有的括号都匹配成功，字符串有效；如果栈不为空，说明还有未匹配的左括号，字符串无效。

代码实现

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character,Character> map = new HashMap<>();

        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        for(char c: s.toCharArray()){
            if(map.containsKey(c))
                stack.push(c);
            else if(stack.isEmpty() || map.get(stack.peek()) != c)
                return false;
            else 
                stack.pop();
        }
        return stack.isEmpty();
    }
}