【Leetcode】678. Valid Parenthesis String（配数学证明）

题目地址：

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

给定一个括号序列$s$，里面除了左右括号之外，还含'*'。'*'可以被当做左右括号，或者空串。问是否存在一种对'*'的替换，使得该序列合法。只需返回true还是false。

动态规划做法可以参考https://blog.csdn.net/qq_46105170/article/details/109269264。下面介绍贪心做法。

法1：贪心。首先回顾一下合法括号序列要满足的条件：
1、左括号右括号数量相等；
2、任意前缀，左括号数量都大于等于右括号数量。
我们定义前缀中左括号减去右括号数叫做“平衡数”。可以开两个变量$l$和$h$，分别记录已经遍历的前缀中，至少还需要消耗多少个左括号与至多还需要消耗多少个左括号。这里消耗可以理解为，遇到个右括号，就从库存里取出个左括号与之配对（消耗）。这里其实是在考虑两个极端的情况，即'*'全变成右括号或者全变成左括号的情况。也就是说，$l$和$h$存的是极端情况下的平衡数。接下来遍历$s$，遇到左括号则$l$和$h$都加$1$；遇到右括号则$l$和$h$都减$1$；遇到'*'，那么如果将其看成左括号，则平衡数加$1$，如果看成右括号，则平衡数减$1$，所以此时我们将$l$减$1$，而将$h$加$1$。每次更新完$l$和$h$以后，如果$h<0$了，返回false；如果$l<0$了，重置$l=0$。遍历完$s$之后，如果$l>0$，返回false，否则返回true。

算法正确性证明：
我们将问题换一种描述。如果将字符串里的左括号看成$1$，右括号看成$-1$，星号看成未知数，那么原问题相当于在问，在每个未知数可以取$-1,0,1$的情况下，是否存在一组解，使得整个$s$等于$0$，并且对于$s$的任何前缀，都是非负的。那么$l$取的是星号全取$-1$的情况，$h$取的是星号全取$1$的情况。如果中途$h<0$了，说明即使星号全取$1$也不能保证前缀和非负，那么应该返回false。如果中途$h\ge 0$，但是$l<0$，那么一定存在一个星号可以由$-1$变为$0$或者由$0$变为$1$（原因在于此时是$h\ge 0$的，星号全变成左括号的时候平衡数是$h$，那将一个星号增加$1$肯定可以使得平衡数变为$0$。这里具体挑哪个星号是无所谓的，哪个都行，但不变不行，因为会使得平衡数变负），也就是说，我们一开始都贪心地将所有的星号都取$-1$，只有在必要时，将某个星号变大，以使得平衡数仍然非负。如果最后遍历完的时候$l=0$，那么按照上述办法去变换星号，就能得到一组合法解，算法正确；如果最后$l>0$，我们取最后一次$l=0$的时刻（这个时刻一定是存在的，因为至少最开始$l=0$），按照上面的调整办法，从这个时刻之前的前缀已经合法，而之后的$l$是该时刻之后的所有星号都取$-1$得到的，如果还有$l>0$的话只能说即使所有星号都取$-1$，左括号仍然要比右括号多，则说明不存在合法解，应该返回false。综上，算法正确。

这里的证明事实上已经给出了一个构造合法解的方法。如果存在合法解，那么构造方法是，先贪心的将所有星号都看成右括号，每当$l<0$的时候，就随便挑一个星号去加一。

代码如下：

public class Solution {
    public boolean checkValidString(String s) {
        int lo = 0, hi = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            
            if (ch == '(') {
                lo++;
                hi++;
            } else if (ch == ')') {
                lo--;
                hi--;
            } else {
                lo--;
                hi++;
            }
            
            if (hi < 0) {
                return false;
            }
            
            lo = Math.max(lo, 0);
        }
    
        return lo == 0;
    }
}

时间复杂度$O(n)$，空间$O(1)$。

法2：栈。开两个栈，分别记录左括号出现的下标和星号出现的下标。接着遍历$s$，如果遇到左括号或者星号，直接将下标进入对应的栈；否则遇到了右括号，如果左括号栈非空则出栈与之配对，如果左括号栈空但星号栈非空则星号栈出栈变为左括号与之配对，如果星号栈也空，那就返回false。遍历完之后，看一下左括号栈是否非空，如果非空，则不停地将下标大于左括号栈顶的星号栈顶出栈，同时也将左括号栈顶出栈；如果发现左括号栈顶是大于星号栈栈顶的，直接返回false。最后左括号栈若空则返回true，否则返回false。这个方法非常直接，哪个要和哪个配对都构造出来了。

算法正确性证明：
首先，我们先证明如果算法返回true，那一定存在一个使得$s$合法的星号的赋值方式。每次星号栈出栈的时候，就将该位置的星号赋值为$1$，这样能保证平衡数一直非负；接着，遍历完$s$之后，pop两个栈的时候，pop出来的星号的赋值方式是$-1$，如果星号栈还非空，则里面的星号全赋值为空串，这样能保证整个字符串的平衡数恰好是$0$。所以就证明了如果算法返回true，那确实存在一个方案。
接下来证明，如果算法返回false，那一定不存在合法方案。首先，如果是遍历$s$的时候返回了false，那说明某个前缀里即使把所有星号都变成左括号，仍然无法保证平衡数为非负，这时当然不存在合法方案；如果遍历完$s$后没有返回false，但最后算法返回false了，我们考虑那个时候括号栈的栈顶的那个左括号，由于在$s$遍历完成之后该左括号仍然没有出栈，说明从该左括号向后的那个后缀的平衡数是大于$0$的，并且即使将其右边所有星号都看成右括号，平衡数也是大于$0$的，所以该左括号无法被右括号匹配，所以不存在合法方案。
综上，算法正确。

代码如下：

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public boolean checkValidString(String s) {
        Deque<Integer> stack = new ArrayDeque<>(), star = new ArrayDeque<>();
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                stack.push(i);
            } else if (ch == '*') {
                star.push(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else if (!star.isEmpty()){
                    star.pop();
                } else {
                    return false;
                }
            }
        }
        
        while (!stack.isEmpty() && !star.isEmpty()) {
            if (stack.peek() < star.peek()) {
                stack.pop();
                star.pop();
            } else {
                return false;
            }
        }
        
        return stack.isEmpty();
    }
}

时空复杂度$O(n)$。

本文地址：https://blog.csdn.net/qq_46105170/article/details/109269287