[刷题防痴呆] 0678 - 有效的括号字符串 (Valid P

题目地址

https://leetcode.com/problems/valid-parenthesis-string/

题目描述

678. Valid Parenthesis String

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".
 

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "(*)"
Output: true
Example 3:

Input: s = "(*))"
Output: true

思路

• 方法1, stack. 维护两个stack. 一个存储左括号的index, 一个存储星号的index. 遇到右括号先匹配左括号, 再匹配星号, 最后看左括号是不是能被星号完全匹配.
• 方法2, 贪心. 用两个变量来维护未匹配的左括号数量可能的最小值和最大值. 如果遇到左括号，则将最小值和最大值分别加1. 如果遇到右括号，则将最小值和最大值分别减1. 如果遇到星号，则将最小值减1，将最大值加1. 遍历中max不能小于0. 最后看min是否为0.

关键点

• 注意, 贪心算法中, minCount的最小值应为0, 因为表示的是到当前位置左括号是否能被匹配完, 如果匹配完就是0. 之后的要再计算. 因此不能为负数.

代码

• 语言支持：Java

// stack
class Solution {
    public boolean checkValidString(String s) {
        Deque<Integer> leftStack = new ArrayDeque<>();
        Deque<Integer> starStack = new ArrayDeque<>();

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

        while (!leftStack.isEmpty() && !starStack.isEmpty()) {
            int leftIndex = leftStack.pop();
            int starIndex = starStack.pop();
            if (starIndex < leftIndex) {
                return false;
            }
        }

        return leftStack.isEmpty();
    }
}

// 贪心
class Solution {
    public boolean checkValidString(String s) {
        int minCount = 0;
        int maxCount = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                minCount++;
                maxCount++;
            } else if (c == '*') {
                minCount = Math.max(minCount - 1, 0);
                maxCount++;
            } else {
                minCount = Math.max(minCount - 1, 0);
                maxCount--;
                if (maxCount < 0) {
                    return false;
                }
            }
        }

        return minCount == 0;
    }
}