有效的括号「变题」

20. 有效的括号

开头先来一个小插曲，关于「括号」相关的总结可见 秒杀所有括号类问题

x
public boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (!st.isEmpty()) {
            if (st.poll() != f(c)) return false;
        } else return false;
    }
    return st.isEmpty();
}
private char f(char c) {
    if (c == ')') return '(';
    else if (c == '}') return '{';
    return '[';
}

变题一：不要求左括号必须以正确的顺序闭合

也就是去掉了 有效的括号 中的要求二！！

🌰 举个例子：[(])这种情况也是满足要求滴！

x
public boolean isValid(String s) {
    int[] cnt = new int[3];
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') cnt[f(c)]++;
        else if (--cnt[f(c)] < 0) return false;
    }
    return cnt[0] == 0 && cnt[1] == 0 && cnt[2] == 0;
}
private int f(char c) {
    if (c == '(' || c == ')') return 0;
    if (c == '[' || c == ']') return 1;
    return 2;
}

变题二：要求必须按 { [ ( 的顺序进行关闭

🌰 举个例子：{[()]}, {}[()]是符合要求的；[{()}]是不符合要求的

换句话说，{的优先级最高，它可以包含其它两种类型的括号；而其它两种类型的括号不能包含它。其它两种同理！

思路：分别为{ [ (设置权重2 1 0，入栈时判断栈顶优先级是否低于当前左括号优先级，如果低于，则非法

xxxxxxxxxx
public boolean isValid(String s) {
    // 技巧：栈中直接存优先级
    Deque<Integer> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        int w = f(c);
        if (c == '(' || c == '[' || c == '{') {
            // 栈不为空 且 栈顶优先级低于 c
            if (!st.isEmpty() && st.peek() < w) return false;
            st.push(w);
        } else if (!st.isEmpty()) {
            if (st.poll() != w) return false;
        } else return false;
    }
    return st.isEmpty();
}
private char f(char c) {
    if (c == '(' || c == ')') return 0; // 低
    if (c == '[' || c == ']') return 1; // 中
    return 2;                           // 高
}