Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

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.
An empty string is also valid.



Example 1:

Input: "()"
Output: True



Example 2:

Input: "(*)"
Output: True



Example 3:

Input: "(*))"
Output: True



Note:

The string size will be in the range [1, 100].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def checkValidString(self, s: str) -> bool:
        

Solutions:
class Solution:

	def checkValidString(self, s):
		(low, high) = (0, 0)
		for c in s:
			if c == '(':
				low += 1
				high += 1
			elif c == ')':
				if low > 0:
					low -= 1
				high -= 1
			else:
				if low > 0:
					low -= 1
				high += 1
			if high < 0:
				return False
		return low == 0


class Solution:

	def checkValidString(self, s):
		rem = {}

		def dfs(i, c):
			if c < 0:
				return False
			elif i == len(s):
				return not c
			elif (i, c) in rem:
				return rem[i, c]
			elif s[i] == '(':
				rem[i, c] = dfs(i + 1, c + 1)
			elif s[i] == ')':
				rem[i, c] = dfs(i + 1, c - 1)
			else:
				rem[i, c] = dfs(i + 1, c) or dfs(i + 1, c - 1) or dfs(i + 1, c + 1)
			return rem[i, c]
		return dfs(0, 0)


class Solution:

	def checkValidString(self, s):
		l = r = star = 0
		for c in s:
			if c == '(':
				l += 1
			if c == ')':
				r += 1
			if c == '*':
				star += 1
			if r > star + l:
				return False
		l = r = star = 0
		for c in s[::-1]:
			if c == '(':
				l += 1
			if c == ')':
				r += 1
			if c == '*':
				star += 1
			if l > star + r:
				return False
		return True


class Solution:

	def checkValidString(self, s):
		open = 0
		star = 0
		count = {'(': 0, ')': 0, '*': 0}
		newS = []
		for i in s:
			if i == ')':
				if open > 0:
					open -= 1
					del newS[len(newS) - 1 - newS[::-1].index('(')]
				elif star > 0:
					star -= 1
					del newS[len(newS) - 1 - newS[::-1].index('*')]
				else:
					return False
			elif i == '(':
				open += 1
				newS += '('
			else:
				star += 1
				newS += '*'
		if star >= open:
			o = 0
			s = 0
			for i in newS:
				if i == '(':
					o += 1
				elif i == '*':
					if o > 0:
						o -= 1
			if o != 0:
				return False
			else:
				return True
		else:
			return False


class Solution:

	def checkValidString(self, s):
		a = 0
		b = 0
		for i in range(len(s)):
			if s[i] == '*':
				a = a + 1
				if b > 0:
					b = b - 1
			elif s[i] == '(':
				a = a + 1
				b = b + 1
			elif s[i] == ')':
				a = a - 1
				if b > 0:
					b = b - 1
			if a < 0:
				return False
		if b == 0:
			return True
		else:
			return False


class Solution:

	def checkValidString(self, s):
		cmin = cmax = 0
		for i in s:
			if i == '(':
				cmax += 1
				cmin += 1
			if i == ')':
				cmax -= 1
				cmin = max(cmin - 1, 0)
			if i == '*':
				cmax += 1
				cmin = max(cmin - 1, 0)
			if cmax < 0:
				return False
		return cmin == 0


class Solution:

	def checkValidString(self, s):
		(lo, hi) = (0, 0)
		for c in s:
			lo += 1 if c == '(' else -1
			hi += 1 if c != ')' else -1
			if hi < 0:
				break
			lo = max(lo, 0)
		return lo == 0