HàPhan 河

Day 16 of 30 days Leetcode Challenge - Valid Parenthesis String

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:
The string size will be in the range [1, 100].


Solution

Use two counter when, meet "(" increase, meet ")" decrease.
First counter assume "*" is "("
Second counter assume "*" is ")"

class Solution {
    func checkValidString(_ s: String) -> Bool {
        var assumeLeft = 0
        var assumeRight = 0
        
        for c in s {
            switch c {
                case "(": 
                    assumeLeft += 1
                    assumeRight += 1
                case ")":
                    if assumeLeft > 0 { assumeLeft -= 1 }
                    assumeRight -= 1
                case "*": 
                    if assumeLeft > 0 { assumeLeft -= 1 }
                    assumeRight += 1
                
                default: break
            }
            
            if assumeRight < 0 { return false }
        }
        
        return assumeLeft == 0
    }
}

Comments