---
# System prepended metadata

title: 678. Valid Parenthesis String
tags: [Leetcode, greedy, medium, python, c++]

---

###### 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:
``` 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++:
``` cpp=
#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;
    }
};
```