C/C++教程

leetcode20-有效的括号(栈+HashMap)

本文主要是介绍leetcode20-有效的括号(栈+HashMap),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

解题思路

【算法原理】

  • 栈先入后出特点恰好与本题括号排序特点一致,即若遇到左括号入栈,遇到右括号时将对应栈顶左括号出栈,则遍历完所有括号后 stack 仍然为空;

  • 建立哈希表 pairs 构建左右括号对应关系:key 左括号,value 右括号;这样查询 2 个括号是否对应只需 O(1) 时间复杂度;建立栈 stack,遍历字符串 s 并按照算法流程判断。

【算法流程】

  1. 如果 ch 是左括号,则入栈 push;

  2. 否则通过哈希表判断括号对应关系,若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 ch 不对应,则提前返回 false。

【代码】

public class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        //奇数
        if (len % 2 == 1) {
            return false;
        }
        //括号键值对
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        //队列
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {   //栈中是否存在对应括号
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {  //判断栈顶与当前是否相等
                    return false;
                }
                stack.pop();   //存在,出栈
            }
            else {
                stack.push(ch);  //入栈
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isValid("()[]{}"));
    }
}
这篇关于leetcode20-有效的括号(栈+HashMap)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!