678. Valid Parenthesis String
约 3 分钟
LeetCode 每日一题：Valid Parenthesis String
本页目录
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"".
Constraints:
1 <= s.length <= 100s[i]is'(',')'or'*'.
思路1: 动态规划
这题没什么思路 看了第一个hints才勉强写出来，我会考虑系统性的攻克一下今天和昨天，这类“寻找最长合法VPS”的习题
python
class Solution:
def checkValidString(self, s: str) -> bool:
memo = [[None]*len(s) for _ in range(len(s))]
def dp(cur, diff):
if diff < 0:
return False
if cur == len(s):
return True if diff == 0 else False
if memo[cur][diff] == None:
if s[cur] == '(':
memo[cur][diff] = dp(cur+1, diff+1)
elif s[cur] == ')':
memo[cur][diff] = dp(cur+1, diff-1)
else:
memo[cur][diff] = dp(cur+1, diff) or dp(cur+1, diff-1) or dp(cur+1, diff+1)
return memo[cur][diff]
return dp(0, 0)思路2：“贪心”
我认为思想上是贪心的，尽可能的不使用星号，因为星号没有副作用，剩下也无妨
python
class Solution:
def checkValidString(self, s: str) -> bool:
p = []
star = []
for i, c in enumerate(s):
if c == '(':
p.append(i)
elif c == '*':
star.append(i)
else:
if p:
p.pop()
elif star:
star.pop()
else:
return False
while p and star:
if p.pop() > star.pop():
# 这里的星号充当右括号，因此要从后往前比较
# 剩下的左括号必须在星号之前出现
return False
return not p # 只允许星号有剩余思路三：还是“贪心”
笔者认为这是另一种贪心方式。这种方法遍历两遍字符串：
- 第一遍，星号全部充当左括号，因此只要每一步diff数量大于等于0，最终结果大于等于0，就视为合法的
- 第二遍，星号全部充当右括号，同理。只是需要倒序遍历，因为这里以右括号为基准了
- 如果在过程中出现了小于0的情况 那必然不合理，舍去就可以
- 如果在过程中没有出现小于零的情况，就一定合理吗？我用AI写了一个绝妙的解释 但是我还是需要时间理解 这里先把代码贴在这里，我感觉除非我再遇到类似的题，我可能这辈子都不会这么想了
python
class Solution:
def checkValidString(self, s: str) -> bool:
# Stacks to store indices of open brackets and asterisks
open_brackets = []
asterisks = []
for i, ch in enumerate(s):
# If current character is an open bracket, push its index onto the stack
if ch == "(":
open_brackets.append(i)
# If current character is an asterisk, push its index onto the stack
elif ch == "*":
asterisks.append(i)
# current character is a closing bracket ')'
else:
# If there are open brackets available, use them to balance the closing bracket
if open_brackets:
open_brackets.pop()
elif asterisks:
# If no open brackets are available, use an asterisk to balance the closing bracket
asterisks.pop()
else:
# nnmatched ')' and no '*' to balance it.
return False
# Check if there are remaining open brackets and asterisks that can balance them
while open_brackets and asterisks:
# If an open bracket appears after an asterisk, it cannot be balanced, return false
if open_brackets.pop() > asterisks.pop():
return False # '*' before '(' which cannot be balanced.
# If all open brackets are matched and there are no unmatched open brackets left, return true
return not open_brackets系列每日一题 →