LeetCode Q 678 - Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

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.
An empty string is also valid.

Example 1: Input: "()" ; Output: True
Example 2: Input: "(*)" ; Output: True
Example 3: Input: "(*))" ; Output: True

Note: The string size will be in the range [1, 100].

Solution:

Solution 1: Brute-Force

Code:

public boolean checkValidString(String s) {
  return helper(s.toCharArray(), 0, 0);
}

private boolean helper(char[] chs, int start, int count) {
  if (count < 0) return false;

  for (int i = start; i < chs.length; i++) {
    if (chs[i] == '(') {
      count++;
    } else if (chs[i] == ')') {
      if (count == 0) return false;
      count--;
    } else {
      return helper(chs, start + 1, count + 1) || helper(chs, start  1, count - 1) || helper(chs, start + 1, count);
    }
  }

  return count == 0;
}

Solution 2: Greedy

If we don’t have '*' in the string, we just need to count '('s and ')'s. Whenever meeting a '(' do count++ and meeting a ')' do count--. When finish traversing the string, check if count==0.

Now, the key point is how to deal with '*', we can regard it as a '(' or as a ')' or just leave it alone. This impacts the count. So when we are at a specific index, the count is not fixed.

We use two constants, one is low, lower bound of count, another is high, upper bound of count.

For low, we take '*' as ')' if there are more '('s.
For high, we take '*' as '('.

So,

if high < 0 means too much ')'s
if low > 0 , after the count finished, means too much '('s.

Code:

public boolean checkValidString(String s) {
  int low = 0, high = 0;
  
  for (char ch: s.toCharArray()) {
    if (ch == '(') {
      low++; high++;
    } else if (ch == ')') {
      if (low > 0) low--;
      high--;
    } else {
      if (low > 0) low--;
      high++;
    }

    if (high < 0) return false;
  }

  return low == 0;
}

Reprint policy