Valid Parenthesis String In 60 Characters
Valid Parenthesis String: Use greedy approach with two counters (minOpen & maxOpen) to track possible open parentheses. If maxOpen < 0 or minOpen > 0 at end, string is invalid.
678. Valid Parenthesis String
Difficulty: Medium
Topics: String, Dynamic Programming, Stack, Greedy
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".
Example 1:
Inp...