題目網址：https://leetcode.cn/problems/valid-parenthesis-string/

題意：給一只包含三種 char （ 、） 和 * 的 string s, 判斷 s 是否為有效的 string。有效的 string 具有如下規則：

  • 任何左括號 ( 必須有相應的右括號 )
  • 任何右括號 ) 必須有相應的左括號 (
  • 左括號 ( 必須在對應的右括號之前 )
  • * 可以被視為單個右括號 ) or 單個左括號 ( or 一個 empty string ""

empty string "" 也被視為有效的 string。

Solution：

想法：利用 Greedy, 由於 * 有三種可能, 因此我們需要用 leftMin、leftMax 來記錄未匹配左括號的範圍

  • leftMax 代表未匹配左括號的最大數量, 也就是將所有 * 都變成 (
  • leftMin 代表未匹配左括號的最小數量, 也就是將所有 * 都變成 )

一旦 leftMax < 0, 代表 s 中 ) 太多, 將所有 * 都變成 ( 也無法匹配, 直接返回 false

一旦 leftMin < 0, 此時的 leftMin 為 -1, 代表不應把所有 * 都設為 )

➔ 而是應該把其中一個 * 設為 "", 以確保 leftMin == 0

  • 將其中一個 從 ) 改為 "", 也就是讓 leftMin + 1

e.g. s = (*)

  • leftMin = -1, 因為 (*) ➔ ()), 但其實可以將 * 從 ) 改為 "", 使得 (*) 變成 ()
  • leftMin = 1, 因為 (*) ➔ (()

遍歷結束時, 所有的左括號都應和右括號匹配。因此只有當 leftMin == 0 時, s 才是有效的

class Solution {
public:
    bool checkValidString(string s) {
        int leftMax = 0; // 未匹配左括號的最大數量, 將所有 * 都變成 (
        int leftMin = 0; // 未匹配左括號的最小數量, 將所有 * 都變成 )

        for (const auto& ch : s) {
            if (ch == '(') {
                ++leftMax;
                ++leftMin;
            } else if (ch == ')') {
                --leftMax;
                --leftMin;
            } else {
                ++leftMax;
                --leftMin;
            }

            if (leftMax < 0) {
                return false;
            }

            if (leftMin < 0) {// (*) -> leftMin = -1, leftMax = 1
                leftMin = 0;
            }
        }

        return leftMin == 0;
    }
};
  • time：$O(n)$ ➔ 遍歷 s, 其中 n 為 s 的長度
  • space：$O(1)$ ➔ 只需常數空間