Skip to content

678. Valid Parenthesis String 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  bool checkValidString(const string& s) {
    int low = 0;   // the lower bound of the number of valid '('s
    int high = 0;  // the upper bound of the number of valid '('s

    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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public boolean checkValidString(final String s) {
    int low = 0;  // the lower bound of the number of valid '('s
    int high = 0; // the upper bound of the number of valid '('s

    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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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