欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【Leetcode】678. Valid Parenthesis String(配数学证明)

程序员文章站 2022-06-18 10:06:01
题目地址:https://leetcode.com/problems/valid-parenthesis-string/给定一个括号序列sss,里面除了左右括号之外,还含'*'。'*'可以被当做左右括号,或者空串。问是否存在一种对'*'的替换,使得该序列合法。只需返回true还是false。动态规划做法可以参考https://blog.csdn.net/qq_46105170/article/details/109269264。下面介绍贪心做法。首先回顾一下合法括号序列要满足的条件:1、左括号右括...

题目地址:

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

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

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

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

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

这里的证明事实上已经给出了一个构造合法解的方法。如果存在合法解,那么构造方法是,先贪心的将所有星号都看成右括号,每当 l < 0 l<0 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(n) O(n),空间 O ( 1 ) O(1) O(1)

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

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

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