Skip to content

Latest commit

 

History

History
121 lines (103 loc) · 4.94 KB

678.valid-parenthesis-string.md

File metadata and controls

121 lines (103 loc) · 4.94 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 *: *(), ()**, **(), *()*.

Breakdowns

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

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.

  • Left parenthesis: we increment the counter.
  • Right parenthesis: 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: 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 because if we use * as (, we increment the counter; if we use it as ), we decrement the counter.

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 ) if possible, 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 ( 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 right if possible
    var leftCountMax = 0 // try to use `*` as left if possible
    for (c in s) {
        if (c == '(') {
            leftCountMin++
            leftCountMax++
        } else if (c == ')') {
            leftCountMin--
            leftCountMax--
        } else { // `*`
            leftCountMin-- // use `*` as right or empty
            leftCountMax++ // Use `*` as left
        }
        
        // We have to handle right > left at this moment, see below 2 cases:

        // 1. If we use all possible `*` as left but `right` still > `left`, that's impossible to match later.
        // Example: "(*)))", we use `*` as left = "(()))", but we can't match the right parenthesis.
        if (leftCountMax < 0) {
            return false
        }

        // 2. We have right > left, but we can alter some `*` from right to left to match.
        // 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