【D15】有效的括号&括号的分数 （LC 20&856）

20. 有效的括号

问题描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

解题思路

引入栈作为辅助数据结构，遍历字符串，依次将左括号入栈；
遇到右括号时，检查它与栈顶元素是否匹配，如果匹配则栈顶元素出栈，遍历继续；
如果栈顶元素为空或者右括号与栈顶元素不匹配，则说明字符串无效。
遍历结束之后，如栈中的所有左括号元素都成功匹配到了右括号，则说明字符串有效。

在Java中，我们用双端队列Deque可以实现Stack的功能：
把元素压栈：push(E)/addFirst(E)；
把栈顶的元素“弹出”：pop(E)/removeFirst()；
取栈顶元素但不弹出：peek(E)/peekFirst()。

• 当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清晰。

代码实现

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList();
        for(int i = 0; i < s.length(); i++){
            Character str = s.charAt(i);
            if(str == '(' || str == '[' || str == '{'){
                stack.push(str);
            }else{
                if(stack.isEmpty() || !isMatch(stack.pop(), str)){
                     return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private boolean isMatch(Character s1, Character s2){
        if( s1 == '{' && s2 == '}'){
            return true;
        }else if(s1 == '[' && s2 == ']'){
            return true;
        }else if(s1 == '(' && s2 == ')'){
            return true;
        }else{
            return false;
        }
    }
}

上述代码判断左右括号是否匹配的逻辑也可以采用HashMap（key为左括号，value为对应的右括号）来实现

class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');

        Deque<Character> stack = new LinkedList();
        for(int i = 0; i < s.length(); i++){
            Character str = s.charAt(i);
            if(str == '(' || str == '[' || str == '{'){
                stack.push(str);
            }else{
                if(stack.isEmpty() || !str.equals(map.get(stack.pop()))){
                     return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

856. 括号的分数

问题描述

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。

解题思路

分析解读S的得分规则：

• 相邻括号对()才会得分；
• 每个相邻括号对所得的分数为其2^n，其中n为括号对左侧的左括号数量（不包括当前相邻括号对的左括号），也就是说n=stack.size() -1
• 平衡括号字符串 S的总得分为其中所有相邻括号对所得分数之和

代码实现

class Solution {
    public int scoreOfParentheses(String S) {
        Deque<Character> stack = new LinkedList<>();
        int sum = 0;

        Character prev = ')';
        for(int i = 0; i < S.length(); i++){
            Character c = S.charAt(i);
            if(c.equals('(')){
                stack.push(c);
            }else{
                //相邻的()才会得分
                if(prev.equals('(')){
                    sum += 1 << (stack.size() -1);
                }
                stack.pop();
            }
            prev = c;
        }
        return sum;
    }
}