###### tags: `Leetcode` `medium` `greedy` `python` `c++`

# 678. Valid Parenthesis String

## [題目連結:] https://leetcode.com/problems/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

## 解題想法:
* 此題為判斷括號字串是否合法:
* ' * '可視為左右括號or空字符

* 貪心法:
* 遍歷字串，**紀錄當前字符需要')'的數量**
* 當前字符為'(': +1
* 當前字符為')': -1
* 因為有萬能' * '，所以需要分別記錄最少與最大值對於')'需要的數量
* 最少需要量minVal:
* **將所有' * '都視為')'**,若minVal為0就不用繼續減了，表示目前左右剛剛好or左邊過多，將' * '視為空字符即可
* 最大需要量maxVal:
* **將所有' * '都視為'('**
* **若為負數，則為False**
* 表示即使' * '都轉為左括號，右括號數量仍太多，不滿足合理左右配對
* 最終判斷:
* 最小值==0 and 最大值!=負數

* Example:

               ( ( * * ) * )
        min    1 2 1 0 0 0 0    
        max    1 2 3 4 3 4 3

## Python:

class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        #紀錄當前字符需要的')'數量 
        #因為有萬能* 所以需要分別記錄最少與最大值 
        #最少值->將所有*都視為')' :若為0就不用繼續減ㄌ
        #最大值->將所有*都視為'(' :若為負數 則為False
        #最終判斷 最小值==0 and 最大值!=負數
        minVal=0
        maxVal=0
        for char in s:
            if char=='(':
                minVal+=1
                maxVal+=1
            elif char==')':
                if minVal>0:
                    minVal-=1
                maxVal-=1
            elif char=='*':
                if minVal>0:
                    minVal-=1
                maxVal+=1
            print('min:',minVal,'max:',maxVal)
            if maxVal<0:
                return False
        return minVal==0
    
if __name__=='__main__':  
    result=Solution()
    s="((**)*)"
    ans=result.checkValidString(s)
    print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool checkValidString(string s) {
        int minNeed=0, maxNeed=0;
        for (char item: s){
            if (item=='('){
                minNeed+=1;
                maxNeed+=1;
            }
            else if (item==')'){
                if (minNeed>0)
                    minNeed-=1;
                maxNeed-=1;
            }
            else if (item=='*'){
                if (minNeed>0)
                    minNeed-=1; //let '*' to be ')'
                maxNeed+=1; //let '*' to be '('
            }
            if (maxNeed<0)
                return false;
        }
        return minNeed==0;
    }
};