0678. Valid Parenthesis String

题目信息

题号:

0678

难度:

Medium

主题:

括号字符串、星号通配、平衡与前缀合法性

原题:

LeetCode 0678

重点:

每个星号可独立解释为左括号、右括号或空串、任意前缀不能出现无法匹配的右括号、最终全部括号必须配对

题目重述

给定只包含 '('、')' 和 '*' 的字符串 s。每个 '*' 可以独立替换为一个左括号、一个右括号,或直接删除为空串。

判断是否存在一种星号解释,使最终字符串成为有效括号字符串:每个左括号都有之后的右括号与之匹配,括号嵌套顺序正确,并且不存在多余括号。s.length 位于 [1, 100]。

自建示例

星号作为右括号:

输入:s = "(*()"
输出:true
解释:把星号解释为右括号后得到 "()()",这是有效括号字符串。

任何解释都无法修复顺序:

输入:s = "*)("
输出:false
解释:星号无论解释为何种字符,都无法同时消除前部多余的右括号和末尾未闭合的左括号。