0678. Valid Parenthesis String¶
题目信息¶
- 题号:
0678
- 难度:
Medium
- 主题:
括号字符串、星号通配、平衡与前缀合法性
- 原题:
- 重点:
每个星号可独立解释为左括号、右括号或空串、任意前缀不能出现无法匹配的右括号、最终全部括号必须配对
题目重述¶
给定只包含 '('、')' 和 '*' 的字符串 s。每个 '*' 可以独立替换为一个左括号、一个右括号,或直接删除为空串。
判断是否存在一种星号解释,使最终字符串成为有效括号字符串:每个左括号都有之后的右括号与之匹配,括号嵌套顺序正确,并且不存在多余括号。s.length 位于 [1, 100]。
自建示例¶
星号作为右括号:
输入:s = "(*()"
输出:true
解释:把星号解释为右括号后得到 "()()",这是有效括号字符串。
任何解释都无法修复顺序:
输入:s = "*)("
输出:false
解释:星号无论解释为何种字符,都无法同时消除前部多余的右括号和末尾未闭合的左括号。