题目主要信息

给定一个字符串s，字符串s只包含以下三种字符: (，*，)，请你判断 s是不是一个合法的括号字符串。合法括号字符串有如下规则:

1.左括号'('必须有对应的右括号')'

2.右括号')'必须有对应的左括号'('

3.左括号必须在对应的右括号前面

4.*可以视为单个左括号，也可以视为单个右括号，或者视为一个空字符

5.空字符串也视为合法的括号字符串

方法一：直接模拟

具体方法

使用栈来模拟，如果没有星的出现，只需要一个栈即可，由于出现了星，这里使用两个栈，一个栈$stack1stack1$和一个$stack2stack2$，其中$stack2stack2$用来存星。

遍历字符串进行如下操作。

• 遇到左括号，下标存入$stack1stack1$栈。
• 如果遇到星号，下标存入$stack2stack2$栈。
• 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
  • 如果左括号栈不为空，则从$stack1stack1$栈弹出栈顶元素；
  • 如果左括号栈为空且星号栈不为空，则从$stack2stack2$栈弹出栈顶元素；
  • 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回$falsefalse$。

最终遍历完，可能两个栈中还有值。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断是否可以匹配，匹配的条件是左括号下标小于星号下标，如果左括号下标大于星号下标则返回 $falsefalse$。

最终判断左括号栈是否为空。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        // write code here
        // 左栈和右栈
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 遇到(
            if (c == '(') {
                stack1.push(i);
            }// 存入星栈 
            else if (c == '*') {
                stack2.push(i);
            } else {
                // 如果栈1不为空 就出栈
                if (!stack1.isEmpty()) {
                    stack1.pop();
                }
                // 如果栈2 不为空可以用*代替 (
                else if (!stack2.isEmpty()) {
                   stack2.pop();
                } else {
                    return false;
                }
            }
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            int leftIndex = stack1.pop();
            int asteriskIndex = stack2.pop();
            if (leftIndex > asteriskIndex) {
                return false;
            }
        }
        return stack1.isEmpty();
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$需要遍历一遍字符串
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，两个栈大小

方法二：贪心

具体方法

直接模拟的空间复杂度比较大，可以通过贪心的思想进行优化。

可以考虑用两个变量记录待消除左括号的最小个数、待消除左括号的最大个数。

$\mathrm{分}\mathrm{别}\mathrm{记}\mathrm{为}min\mathrm{和}max\mathrm{，}\mathrm{只}\mathrm{要}min\mathrm{为}0\mathrm{，}\mathrm{说}\mathrm{明}\mathrm{左}\mathrm{括}\mathrm{号}\mathrm{能}\mathrm{全}\mathrm{部}\mathrm{消}\mathrm{除}\mathrm{，}\mathrm{字}\mathrm{符}\mathrm{串}\mathrm{合}\mathrm{法}\mathrm{。}分别记为min和max，只要min为0，说明左括号能全部消除，字符串合法。$

遍历整个字符串，如果遇到左括号，则[min,max]范围内所有数均加1，所以min加1，max加1。

$\mathrm{遇}\mathrm{到}\mathrm{右}\mathrm{括}\mathrm{号}\mathrm{，}\mathrm{则}[min,max]\mathrm{范}\mathrm{围}\mathrm{内}\mathrm{所}\mathrm{有}\mathrm{数}\mathrm{均}\mathrm{减}1\mathrm{，}\mathrm{所}\mathrm{以}遇到右括号，则[min,max]范围内所有数均减1，所以$min$\mathrm{减}1\mathrm{（}\mathrm{前}\mathrm{提}\mathrm{是}min\mathrm{大}\mathrm{于}0\mathrm{）}\mathrm{，}max\mathrm{减}1\mathrm{（}\mathrm{如}\mathrm{果}max\mathrm{已}\mathrm{经}\mathrm{是}0\mathrm{，}\mathrm{说}\mathrm{明}\mathrm{没}\mathrm{有}\mathrm{左}\mathrm{括}\mathrm{号}{\mathrm{或}}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}\mathrm{号}\mathrm{与}\mathrm{当}\mathrm{前}\mathrm{右}\mathrm{括}\mathrm{号}\mathrm{匹}\mathrm{配}\mathrm{，}\mathrm{返}\mathrm{回}false\mathrm{）}\mathrm{。}\mathrm{如}\mathrm{果}\mathrm{遇}{\mathrm{到}}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}\mathrm{号}\mathrm{，}\mathrm{则}min\mathrm{减}1\mathrm{（}\mathrm{前}\mathrm{提}\mathrm{是}min\mathrm{大}\mathrm{于}0\mathrm{）}\mathrm{，}max\mathrm{加}1减1（前提是min大于0），max减1（如果max已经是0，说明没有左括号或\text{'}*\; \text{'}号与当前右括号匹配，返回false）。如果遇到\text{'}*\text{'}号，则min减1（前提是min大于0），max加1$。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        // write code here
        int min = 0, max = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            //如果遇到左括号，则将最小值和最大值分别加 1；
            if (c == '(') {
                min++;
                max++;
            }//如果遇到右括号，则将最小值和最大值分别减 1； 
            else if (c == ')') {
                min = Math.max(min - 1, 0);
                max--;
                if (max < 0) {
                    return false;
                }
            }//如果遇到星号，则将最小值减 1，将最大值加 1
            else {
                min = Math.max(min - 1, 0);
                max++;
            }
        }
        return min == 0;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$需要遍历一遍字符串
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$，临时变量大小