解題程式碼

var checkValidString = function (s) {
  let leftMin = 0;
  let leftMax = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      leftMin++;
      leftMax++;
    } else if (s[i] === ')') {
      leftMin--;
      leftMax--;
    } else {
      leftMin--; // * become ')'
      leftMax++; // * become '('
    }
    if (leftMax < 0) return false; // ')' more than '('
    if (leftMin < 0) leftMin = 0; // some '*' should become '' instead of ')'
  }

  return leftMin === 0;
};

兩個 Stack:

Beats 100% | Two stack Solution

兩個 stack，非最佳解

var checkValidString = function (s) {
  const openStack = [];
  const starStack = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === ')') {
      if (openStack.length > 0) {
        openStack.pop();
      } else if (starStack.length > 0) {
        starStack.pop();
      } else {
        return false;
      }
    } else if (s[i] === '(') {
      openStack.push(i);
    } else {
      starStack.push(i);
    }
  }

  while (openStack.length) {
    if (openStack[openStack.length - 1] < starStack[starStack.length - 1]) {
      openStack.pop();
      starStack.pop();
    } else {
      return false;
    }
  }

  return true;
};

解題思路、演算法

最佳解是用兩個變數儲存 '(' 出現的最少和最多次的次數 leftMin & leftMax。

然後碰到 '(' 會做抵銷，兩個變數都減一，碰到 * 則會變成 '(' 或 ')'，所以將兩個變數次數分別做加減。

leftMax 若小於 0，代表 ')' 出現次數多於 '('，回傳 false。

leftMin 若小於 0 且 leftMax 不小於 0，代表 * 轉換過多的 ')'，應該當作轉換成 ''，故歸 0。

最後迴圈結束，確認是否還有 '(' 沒被抵銷(leftMin)。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

Valid Parenthesis String - Leetcode 678 - Python