← 返回 bytedance 的题目列表Validate Parentheses with Wildcards (*)
类型：online_judge
Given a string s containing only '(', ')', and '*'. The '*' character can be treated as '(', ')', or the empty string "".
Determine whether there exists a replacement of '*' such that s becomes a valid parentheses string (for every prefix, number of '(' is at least number of ')', and total counts are equal at the end).
Input: one line string s
Output: true or false
Constraints: 1 <= len(s) <= 1e5
Examples
Input: (*)
Output: true
Input: (*))
Output: true
Example
Input
(*)
Output
true