Valid Parenthesis String

Description

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].

Solution(javascript)

/*
 * @lc app=leetcode id=678 lang=javascript
 *
 * [678] Valid Parenthesis String
 */

// // @lc code=start
// /** 1.1: Greedy
//  * @param {string} s
//  * @return {boolean}
//  */
// const checkValidString = function (s) {
//   let lo = 0
//   let hi = 0
//   for (const c of s) {
//     if (c === '(') {
//       lo += 1
//       hi += 1
//     } else if (c === ')') {
//       if (lo > 0) {
//         lo--
//       }
//       hi -= 1
//     } else {
//       if (lo > 0) {
//         lo--
//       }
//       hi++
//     }
//     if (hi < 0) {
//       return false
//     }
//   }
//   return lo === 0
// }

// @lc code=start
/** 1.2: Greedy
 * @param {string} s
 * @return {boolean}
 */
const checkValidString = function (s) {
  let balance = 0
  for (const c of s) {
    if (c === '(' || c === '*') {
      balance += 1
    } else if (c === ')') {
      balance -= 1
    }
    if (balance < 0) {
      return false
    }
  }
  balance = 0
  for (let i = s.length - 1; i >= 0; i--) {
    const c = s[i]
    if (c === ')' || c === '*') {
      balance += 1
    } else if (c === '(') {
      balance -= 1
    }
    if (balance < 0) {
      return false
    }
  }
  return true
}
// @lc code=end