【Leetcode】678. Valid Parenthesis String（配數學證明）

題目位址：

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 h≥0，但是 l < 0 l<0 l<0，那麼一定存在一個星号可以由 − 1 -1 −1變為 0 0 0或者由 0 0 0變為 1 1 1（原因在于此時是 h ≥ 0 h\ge 0 h≥0的，星号全變成左括号的時候平衡數是 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)。