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

import java.util.*;

/**
 * NC175 合法的括号字符串
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValidString (String s) {
        return solution1(s);
        // return solution2(s);
    }

    /**
     * 栈
     * @param s
     * @return
     */
    private boolean solution1(String s){
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> starStack = new Stack<>();

        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                leftStack.push(i);
            }
            if(s.charAt(i) == '*'){
                starStack.push(i);
            }
            if(s.charAt(i) == ')'){
                if(!leftStack.isEmpty()){
                    leftStack.pop();
                }else if(!starStack.isEmpty()){
                    starStack.pop();
                }else{
                    return false;
                }
            }
        }

        while(!leftStack.isEmpty()){
            if(!starStack.isEmpty() && leftStack.peek()<starStack.peek()){
                leftStack.pop();
                starStack.pop();
            }else{
                return false;
            }
        }

        return true;
    }

    /**
     * 贪心
     * @param s
     * @return
     */
    private boolean solution2(String s){
        // 待消除左括号的最小个数
        int minLeft = 0;
        // 待消除左括号的最大个数
        int maxLeft = 0;

        for(char ch: s.toCharArray()){
            if(ch == '('){
                minLeft++;
                maxLeft++;
            }
            if(ch == '*'){
                // * -> )
                if(minLeft > 0){
                    minLeft--;
                }
                // * -> (
                maxLeft++;
            }
            if(ch == ')'){
                if(minLeft > 0){
                    minLeft--;
                }
                // 已经没有'('或'*'与当前')'匹配
                if(maxLeft == 0){
                    return false;
                }
                maxLeft--;
            }
        }

        return minLeft==0;
    }
}