题解 | #合法的括号字符串#

题意整理

给定一个字符串s，字符串s只包含三种字符: '('，'*'，')'。
判断s是不是一个合法的括号字符串。
合法的条件是：每一个左括号必须有一个右括号与之匹配，每一个右括号必须有一个左括号与之匹配。匹配的左括号必须在右括号前面。'*'号可以视为左括号、可以视为右括号、也可以视为空字符。空字符视为合法的括号字符串。

方法一（栈）

1.解题思路

新建两个栈left、star，分别记录未匹配的左括号和'*'号对应下标
遍历整个字符串，如果是左括号，则将下标入left栈。如果是'*'号，则将下标入star栈。如果是右括号，先拿left栈里元素抵消，再拿star栈的元素抵消，都没有，则返回false。
接着通过循环，检查未匹配的左括号和'*'号。每一个左括号都必须有一个'*'号（视为右括号）与之匹配，如果匹配不上，则返回false。
最后如果left栈为空，说明左括号全部匹配上，而之前也检查了所有的右括号。所以字符串合法。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        //新建两个栈left、star，分别记录未匹配的左括号和*号对应下标
        LinkedList<Integer> left=new LinkedList<>();
        LinkedList<Integer> star=new LinkedList<>();
        int n=s.length();
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            //左括号下标入栈
            if(c=='('){
                left.push(i);
            }
            //*号下标入栈
            else if(c=='*'){
                star.push(i);
            }
            //如果是右括号
            else{
                //首先匹配左括号
                if(!left.isEmpty()){
                    left.pop();
                }
                //其次匹配*号
                else if(!star.isEmpty()){
                    star.pop();
                }
                //如果都没有，说明有右括号找不到匹配对象
                else{
                    return false;
                }
            }
        }
        //检查未匹配的左括号和*号
        while(!left.isEmpty()&&!star.isEmpty()){
            int top1=left.pop();
            int top2=star.pop();
            //每一个左括号都必须有一个*号（视为右括号）与之匹配
            if(top1>top2){
                return false;
            }
        }
        return left.isEmpty();
    }
}

3.复杂度分析

时间复杂度：每一个左括号和'*'号只可能入栈和出栈一次，如果字符串长度为n，则最多执行 $2 * n$ 次入栈或出栈操作，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外大小为 $n$ 的left栈和star栈，所以空间复杂度为 $O (n)$ 。

方法二（贪心）

1.解题思路

可以考虑用两个变量记录待消除左括号的最小个数、待消除左括号的最大个数。分别记为minCount和maxCount，最后只要minCount为0，说明左括号能全部消除，字符串合法。遍历整个字符串，如果遇到左括号，则[minCount,maxCount]范围内所有数均加1，所以minCount加1，maxCount加1。遇到右括号，则[minCount,maxCount]范围内所有数均减1，所以minCount减1（前提是minCount大于0），maxCount减1（如果maxCount已经是0，说明没有左括号或'*'号与当前右括号匹配，返回false）。如果遇到'*'号，则minCount减1（前提是minCount大于0），maxCount加1。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        //待消除左括号的最小个数
        int minCount=0;
        //待消除左括号的最大个数
        int maxCount=0;
        int n=s.length();
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            //如果是左括号，minCount和maxCount均加1
            if(c=='('){
                minCount++;
                maxCount++;
            }
            //如果是右括号，minCount和maxCount均减1
            else if(c==')'){
                if(minCount>0){
                    minCount--;
                }
                if(maxCount==0){
                    return false;
                }
                maxCount--;
            }
            //如果是*号，minCount减1，maxCount加1
            else{
                if(minCount>0){
                    minCount--;
                }
                maxCount++;
            }
        }
        //只要minCount为0，说明左括号能全部抵消掉，字符串合法
        return minCount==0;
    }
}

3.复杂度分析

时间复杂度：只需遍历整个字符串一次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。