Leetcode

Valid Parenthesis String

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  bool checkValidString(const string& s) {
    int low = 0;   // lower bound of valid '(' count
    int high = 0;  // upper bound of valid '(' count

    for (const char c : s) {
      switch (c) {
        case '(':
          ++low;
          ++high;
          break;
        case ')':
          low = max(0, --low);
          --high;
          break;
        case '*':
          low = max(0, --low);
          ++high;
          break;
      }
      if (high < 0)
        return false;
    }

    return low == 0;
  }
};

JAVA

class Solution {
  public boolean checkValidString(final String s) {
    int low = 0;  // lower bound of valid '(' count
    int high = 0; // upper bound of valid '(' count

    for (final char c : s.toCharArray()) {
      switch (c) {
        case '(':
          ++low;
          ++high;
          break;
        case ')':
          low = Math.max(0, --low);
          --high;
          break;
        case '*':
          low = Math.max(0, --low);
          ++high;
          break;
      }
      if (high < 0)
        return false;
    }

    return low == 0;
  }
}

Python

class Solution:
  def checkValidString(self, s: str) -> bool:
    low = 0
    high = 0

    for c in s:
      if c == '(':
        low += 1
        high += 1
      elif c == ')':
        if low > 0:
          low -= 1
        high -= 1
      else:
        if low > 0:
          low -= 1
        high += 1
      if high < 0:
        return False

    return low == 0