leetcode算法题-有效的括号

题目

本题为leetcode探索初级算法中其它章节的一题

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

有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

我的解法

class Solution {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if(aChar == '(' || aChar == '{' || aChar == '['){
                stack.push(aChar);
            }
            if(aChar == ']'){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop == null || !pop.equals('[')){
                    return false;
                }
            }
            if( aChar == '}'){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop == null || !pop.equals('{')){
                    return false;
                }
            }
            if(aChar == ')'){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop == null || !pop.equals('(')){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

这道题想到用栈,问题就不大了。

官方解法

public boolean isValid(String s) {
        int n = s.length();
        if (n % 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 < n; 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();
    }
}

时间复杂度:O(n)O(n),其中 nn 是字符串 ss 的长度。

空间复杂度:O(n + |\Sigma|)O(n+∣Σ∣),其中 \SigmaΣ 表示字符集,本题中字符串只包含 66 种括号,|\Sigma| = 6∣Σ∣=6。栈中的字符数量为 O(n)O(n),而哈希映射使用的空间为 O(|\Sigma|)O(∣Σ∣),相加即可得到总空间复杂度。

与官方相比大致思路相同,官方中先判断了长度,题目中前提是“只包括”所以长度为奇数肯定是false。
另外用到了map简化了if-else判断。

上一篇:c++与java中子类中调用父类成员的方法


下一篇:Jmeter 响应 uncode 编码转为中文