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:

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

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

Analyze

the key point of this description is this line:

'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

if there is no ‘*’, we can simply use a const number to map the string, increase by one when ‘(‘ and decrease with ‘)’.

However, the ‘*’ could be ‘(‘,’)’,and empty string.

AC code

Approach #1

we use two stacks in this solution, one to record the index of the ‘(‘, the other is used to record the index of ‘*’ . when it comes to ‘)’, if there is left bucket ,we pop one from the left stack, if there is no left bucket, we pop a star from the stack to be used as ‘(‘. if there is no star either, we can simply return false.

After the iteration, we compare the top of the two stacks. Since a string end up with ‘*(‘ is definitely not valid. Then we continually pop an item from both stacks until one of this is empty. Finally if there is still left bucket, the string is invalid, otherwise, it is valid.

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  const array = s.split("");
  let p = {
    leftArr: [],
    starArr: []
  };
  for (let i = 0; i < array.length; i++) {
    if (array[i] === "*") {
      p.starArr.push(i);
    } else if (array[i] === ")") {
      if (p.leftArr.length === 0) {
        if (p.starArr.length === 0) {
          return false;
        } else {
          p.starArr.pop();
        }
      } else {
        p.leftArr.pop();
      }
    } else if (array[i] === "(") {
      p.leftArr.push(i);
    }
  }
  while (p.leftArr.length && p.starArr.length) {
    if (p.leftArr.pop() > p.starArr.pop()) {
      return false;
    }
  }
  return !p.leftArr.length;
};

Complexity Analysis

  • Time Complexity: O(N)
  • Space Complexity: O(N).

Approach #2

we iterate the array twice,using two varible to record the result .The first time we iterate it from left to right, treating all star as left bucket, if n<0, it means the sum of left bucket and the star is less than the sum of right bucket, so return false. The second time we iterate the array reversed, treated all star as right bucket. Same, if m<0, simply return false. After the iterations, we consider this array to be valid.

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  const array = s.split("");
  let n = 0,
    m = 0;
  for (let i = 0; i < array.length; i++) {
    if (array[i] === "*" || array[i] === "(") {
      n++;
    } else {
      n--;
    }
    if (n < 0) {
      return false;
    }
  }

  for (let i = array.length - 1; i >= 0; i--) {
    if (array[i] === "*" || array[i] === ")") {
      m++;
    } else {
      m--;
    }
    if (m < 0) {
      return false;
    }
  }

  return true;
};

Complexity Analysis

  • Time Complexity: O(N^2),
  • Space Complexity: O(1).

Approach #3 Greedy

Intuition

When checking whether the string is valid, we only cared about the “balance“: the number of extra, open left brackets as we parsed through the string. For example, when checking whether ‘(()())’ is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through the string: '(' has 1 left bracket, '((' has 2, '(()' has 1, and so on. This means that after parsing the first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.

For example, if we have string '(***)', then as we parse each symbol, the set of possible values for the balance is [1] for '('; [0, 1, 2] for '(*'; [0, 1, 2, 3] for '(**'; [0, 1, 2, 3, 4] for '(***', and [0, 1, 2, 3] for '(***)'.

Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].

Algorithm

Let lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

If we encounter a left bracket (c == '('), then lo++, otherwise we could write a right bracket, so lo--. If we encounter what can be a left bracket (c != ')'), then hi++, otherwise we must write a right bracket, so hi--. If hi < 0, then the current prefix can’t be made valid no matter what our choices are. Also, we can never have less than 0 open left brackets. At the end, we should check that we can have exactly 0 open left brackets.

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  const array = s.split("");
  let low = 0,
    high = 0;
  for (let i = 0; i < array.length; i++) {
    if (array[i] === "(") {
      low++;
      high++;
    } else if (array[i] === ")") {
      if (low > 0) {
        low--;
      }
      high--;
    } else {
      if (low > 0) {
        low--;
      }
      high++;
    }

    if (high < 0) {
      return false;
    }
  }

  return low === 0;
};

Complexity Analysis

  • Time Complexity: O(N)
  • Space Complexity: O(1)