Skip to content

Latest commit

 

History

History
124 lines (105 loc) · 4.99 KB

678.valid-parenthesis-string.md

File metadata and controls

124 lines (105 loc) · 4.99 KB

678. Valid Parenthesis String

Test Cases

Edge Cases

  • No *: "", (), ())
  • Balanced * + valid string: ``, (), ``, `()`, `()()*`
  • All *: ***, always valid.
  • More ) than possible *: ()*))), impossible to be valid.
  • Leading or trailing *: *(), ()**, **(), *()*.

Key Insights

Question: If we don't have *, how to check if the string is balanced?

We can simply use a counter to count the number of unmatched left parenthesis. It's similar idea from 921. Minimum Add to Make Parentheses Valid.

  • L: we increment the counter.
  • R: we decrement the counter.

And we have check if right > left during the iteration and left == 0 at the end.

  • right > left: Too many right, it's impossible to match later even if we still have parenthesis.
  • left != 0: Too many left, it's impossible to match at the end.
fun checkValidString(s: String): Boolean {
    var leftCount = 0 // unmatched left parenthesis
    for (c in s) {
        if (c == '(') {
            leftCount++
        } else if (c == ')') {
            leftCount--
        }
        
        // If right > left, it's impossible to match later
        if (leftCount < 0) {
            return false
        }
    }
    // We must balance all left parenthesis at the end
    return leftCount == 0
}

Stack (Greedy)

Based on this idea, we can extend the idea to include * which can be either (, ) or empty. It will affect the number of unmatched left parenthesis based on how we use * as L (leftCount++) or R (leftCount--).

  • If we use all * as L, then the left count will be maximum.
  • If we use all * as R, then the left count will be minimum.

The left count varies based on our choice of *, so we need to track the possible range of unmatched left parenthesis, we can use two counters as lower and upper bounds to keep track of the number of unmatched left parenthesis:

  • Minimum of left count (lower bound): If we use all * as R, we can match as many ( as possible, so the left count will be minimum. Then all the remaining ( parenthesis MUST be matched.
  • Maximum of left count (upper bound): If we use all * as L if possible, then some left parenthesis COULD be matched. If there are too many (, we just alter some * to ) to match the left parenthesis.

And we can modify the above code to handle the * case:

fun checkValidString(s: String): Boolean {
    var leftCountMin = 0 // try to use `*` as R if possible
    var leftCountMax = 0 // try to use `*` as L if possible
    for (c in s) {
        if (c == '(') {
            leftCountMin++
            leftCountMax++
        } else if (c == ')') {
            leftCountMin--
            leftCountMax--
        } else { // `*`
            leftCountMin-- // use `*` as R or empty
            leftCountMax++ // Use `*` as L
        }
        
        // We have to handle right > left at this moment, see below 2 cases:

        // 1. We use all `*` as L, but R is still > L, impossible to be balanced later.
        // Example: "(*)))", we use `*` as left = "(()))", but we can't match the right parenthesis.
        if (leftCountMax < 0) {
            return false
        }

        // 2.  We use all * as R, but R > L, we can alter some * to be L to balance.
        // Example: "()**", minimum is to use * as `)` = "()))", there are too many `)`,
        // we alter the first `*` to `(` to match the right parenthesis = "(())".
        if (leftCountMin < 0) {
            leftCountMin = 0 // It becomes balanced again.
        }
    }
    // For balanced string, leftCountMin <= leftCountMax at any moment
    // The parentheses are balanced if `0 <= [leftCountMin, leftCountMax]`
    // If lelftCountMin != 0, that means we use all `*` as right but still have unmatched left parenthesis.
    // But we allow max count != 0 because we can alter `*` to match the left parenthesis.
    return leftCountMin == 0
}

WA

It failed by simply counting the *. Failed case: **((, the count of * is 2, but it's invalid because we can't match the left parenthesis when using * as right.

fun checkValidString(s: String): Boolean {
    var leftCount = 0
    var starCount = 0
    for (c in s) {
        if (c == '*') starCount++
        else if (c == '(') {
            leftCount++
        } else {
            leftCount--
        }

        if (leftCount < 0) {
            if (starCount + leftCount >= 0) {
                starCount += leftCount
                leftCount = 0
            } else {
                return false
            }
        }
    }
    return starCount >= leftCount
}

TODO: Another simple solution: https://leetcode.cn/problems/valid-parenthesis-string/solutions/992542/tan-xin-zhi-jie-zhuan-hua-xing-hao-by-no-96j6/

Reference