leetcode - 678. Valid Parenthesis String

Description

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 "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

Solution

Stack

Use 2 stacks, one for opening parenthesis, one for stars. When the current character is a closing parenthesis, pop from the opening parenthesis first, then the star. After iterating the string, pop from the opening parenthesis and star, for every opening parenthesis, if there is a star at the right, then it’s valid.

Time complexity: $o(n)$
Space complexity: $o(n)$

Two pointers

Solved after help.

Use cmin to denote the count of ( we must pair, and cmax to denote the count of ( at most we need to pair. So when the current character is (, we increase both of them by 1, when it’s ) we decrease by 1, when it’s *, we decrease cmin by 1 (the star will work as )), and increase cmax by 1 (the star will work as ().

During this process, the cmax can’t be negative, and in the end, the cmin needs to be 0.

Here’s a graph from this solution:

Time complexity: $o(n)$
Space complexity: $o(1)$

Code

Stack

class Solution:def checkValidString(self, s: str) -> bool:star_stack = []opening_stack = []for i, each_c in enumerate(s):if each_c == '(':opening_stack.append(i)elif each_c == ')':if opening_stack:opening_stack.pop()elif star_stack:star_stack.pop()else:return Falseelse:star_stack.append(i)while opening_stack:if not star_stack:return Falseopening_i, star_i = opening_stack.pop(), star_stack.pop()if star_i < opening_i:return Falsereturn True

Two pointers

class Solution:def checkValidString(self, s: str) -> bool:cmin, cmax = 0, 0for each_c in s:if each_c == '(':cmin += 1cmax += 1elif each_c == ')':cmin -= 1cmax -= 1else:cmin -= 1cmax += 1if cmax < 0:return Falsecmin = max(0, cmin)return cmin == 0