# 資訊

:::info
- Question: 678. Valid Parenthesis String
- From: Leetcode Daily Challenge 2024.04.07
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:
:::success
* Input: `s = "()"`
* Output: true
:::

> Example 2:
:::success
* Input: `s = "(*)"`
* Output: true
:::

> Example 3:
:::success
* Input: `s = "(*))"`
* Output: true
:::

> Constraints:
:::success
* 1 <= `s.length` <= 100
* `s[i]` is `'('`, `')'` or `'*'`.
:::

---

# 解法

## 概念

> Ref: [Click me](https://leetcode.com/problems/valid-parenthesis-string/solutions/4985006/96-98-easy-solution-with-explanation)

有萬用字元一切就變得複雜了，直接說明程式碼怎麼達成今天的 daily challenge！

首先有兩個變數 `leftMin` 和 `leftMax` 紀錄數值，`leftMin` 指出括號配對最少的情況，而 `leftMax` 指出括號配對最多的情況。

當遇到一個 `'('`，就把 `leftMin` 和 `leftMax` 往上加一，因為左括號多了一個；當遇到一個 `')'`，就把 `leftMin` 和 `leftMax` 往下減一，因為右括號可以跟左括號抵銷，如果是遇到 `'*'`，就把 `leftMin` 減一，這邊對於 `leftMin` 而言 `'*'` 是右括號，把 `leftMax` 加一，這邊對於 `leftMax` 而言 `'*'` 是左括號。其中每一輪都會去檢查 `leftMax` 值有沒有小於 0，有代表右括號數量多於左括號與星號總數量，這是不合理的，所以應該 return false；另外也會看 `leftMin` 的值是否小於零，如果小於零就要把他重設回零，因為我們預設 `'*'` 是右括號，所以才會說遇到 `'*'`，就把 `leftMin` 減一，但當不合理的時候就知道那個 `'*'` 要作為空字串，所以直接 reset 回零即可

最後要判斷 `leftMin` 是不是等於零，代表括號數是對稱的，所以可以 return true，否則 `leftMin` 大於零代表左括號太多，應該 return false，`leftMin` 不會小於零，因為會在程式碼第 18 到 19 行就設為零。

## 程式碼

class Solution:
    def checkValidString(self, s: str) -> bool:
        leftMin = 0
        leftMax = 0
        for i in range(len(s)):
            if s[i] == '(':
                leftMin += 1
                leftMax += 1
            elif s[i] == ')':
                leftMin -= 1
                leftMax -= 1
            else:   # s[i] == '*'
                leftMin -= 1
                leftMax += 1
            
            if leftMax < 0:
                return False
            if leftMin < 0:
                leftMin = 0
        return leftMin == 0

---

# 複雜度

## 時間複雜度

因為走過整個字串，所以是 $O(n)$


## 空間複雜度

因為只有兩個變數 `leftMin` 和 `leftMax`，所以是 $O(1)$