题目

678. 有效的括号字符串 (中等)

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
星号*可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

示例 1:

输入: "()"
输出: True

示例 2:

输入: "(*)"
输出: True

示例 3:

输入: "(*))"
输出: True

注意:
字符串大小将在 [1，100] 范围内。

题解

方法一

import java.util.Stack;

/**
 * 时间: 2021-09-12 13:48
 * 分析: 根据给定规则判断字符串的合法性
 * 思路:
 *  1. 通过双指针校验
 *  2. 通过两个栈处理
 *  3. 统计三个符号的数量, 如果左右括号之差小于等于星号数量则是合法的
 * 参考:
 *  1. 动态规划
 *  2. 栈解决 (当前实现)
 *  3. 贪心算法
 * 难点: 怎么出*号
 */
class Solution0678 {
    public boolean checkValidString(String s) {
        Stack<Integer> left = new Stack<>();
        Stack<Integer> symbol = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            switch (ch) {
                case '(': left.push(i); break;
                case '*': symbol.push(i); break;
                default: {
                    if (!left.isEmpty()) {
                        left.pop();
                    } else if (!symbol.isEmpty()) {
                        symbol.pop();
                    } else {
                        return false;
                    }
                    break;
                }
            }
        }

        while (!left.isEmpty() && !symbol.isEmpty()) {
            int leftIdx = left.pop();
            int symbolIdx = symbol.pop();
            if (leftIdx > symbolIdx) {
                return false;
            }
        }

        return left.isEmpty();
    }
}

方法二

/**
 * 时间: 2021-09-12 13:48
 * 分析: 根据给定规则判断字符串的合法性
 * 思路:
 *  1. 通过双指针校验
 *  2. 通过两个栈处理
 *  3. 统计三个符号的数量, 如果左右括号之差小于等于星号数量则是合法的
 * 参考:
 *  1. 动态规划
 *  2. 栈解决
 *  3. 贪心算法 (当前实现)
 * 难点: 怎么出*号
 */
class Solution0678_1 {
    public boolean checkValidString(String s) {
        // 记录需要匹配的右括号数量
        int min = 0, max = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                min++;
                max++;
            } else if (ch == ')') {
                min = Math.min(min, min - 1);
                max--;
                if (max < 0) {
                    return false;
                }
            } else {
                min = Math.min(min, min - 1);
                max++;
            }
        }

        return min == 0;
    }
}

Q.E.D.