All problems

Valid Parenthesis String

Medium · greedy

A string s contains only the characters (, ) and *. Each * is a wildcard: it can be replaced by a (, by a ), or removed completely (replaced by nothing).

A string made only of brackets is balanced when every ( is closed by a later ), every ) closes an earlier (, and brackets nest properly, as in (()()). The empty string is balanced.

Return true if the wildcards can be replaced so that the whole string becomes balanced, and false otherwise.

Examples

Example 1

Input: s = "(*)"

Output: true

Replace the * with nothing to get "()".

Example 2

Input: s = "(*))"

Output: true

Replace the * with ( to get "(())".

Example 3

Input: s = "*(("

Output: false

Both ( are never closed, and the * before them cannot close anything.

Constraints