难度: Medium
原题连接
内容描述
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].
思路 1 - 时间复杂度: O(N^3)- 空间复杂度: O(N^2)******
Let dp[i][j] be true if and only if the interval s[i], s[i+1], ..., s[j] can be made valid. Then dp[i][j] is true only if:
s[i] is '*', and the interval s[i+1], s[i+2], ..., s[j] can be made valid;
or, s[i] can be made to be '(', and there is some k in [i+1, j] such that s[k] can be made to be ')', plus the two intervals cut by s[k] (s[i+1: k] and s[k+1: j+1]) can be made valid;
因为文章要从垃圾算法写到好的算法，这不是我的第一解法
但是是真的垃圾，才beats 2.75%
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
if not s or len(s) == 0:
return True
LEFTY, RIGHTY = '(*', ')*'
n = len(s)
dp = [[0] * n for _ in s]
for i in range(n):
if s[i] == '*':
dp[i][i] = 1
if i < n-1 and s[i] in LEFTY and s[i+1] in RIGHTY:
dp[i][i+1] = 1
for j in range(n):
for i in range(j-2, -1, -1):
if s[i] == '*' and dp[i+1][j]:
dp[i][j] = 1
elif s[i] in LEFTY:
for k in range(i+1, j+1):
if s[k] in RIGHTY and \
(k == i+1 or dp[i+1][k-1]) and \
(k == j or dp[k+1][j]):
dp[i][j] = 1
return True if dp[0][-1] else False或者后面的循环按照子串的长度size来遍历，
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
if not s or len(s) == 0:
return True
LEFTY, RIGHTY = '(*', ')*'
n = len(s)
dp = [[False] * n for _ in s]
for i in range(n):
if s[i] == '*':
dp[i][i] = True
if i < n-1 and s[i] in LEFTY and s[i+1] in RIGHTY:
dp[i][i+1] = True
for size in range(2, n):
for i in range(n - size):
if s[i] == '*' and dp[i+1][i+size]:
dp[i][i+size] = True
elif s[i] in LEFTY:
for k in range(i+1, i+size+1):
if (s[k] in RIGHTY and \
(k == i+1 or dp[i+1][k-1]) and \
(k == i+size or dp[k+1][i+size])):
dp[i][i+size] = True
return dp[0][-1]思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
这是我的最初方法
- Keep track of indices for unmatched '(' and available '*'.
- After the loop we can check whether the index of any remaining '*' can match the unmatched '('.
- If the index of star is greater than the index of '(' then they can match.
beats 100%
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
if not s or len(s) == 0:
return True
stack, star = [], []
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
elif s[i] == ')':
if stack:
stack.pop()
elif star:
star.pop()
else:
return False
else:
star.append(i)
while stack and star:
# 从后面开始比较，如果最后出现的'('的index比最后出现的'*'更大，那其实这个匹配不了，比如'*('
if stack[-1] > star[-1]:
return False
else:
stack.pop()
star.pop()
return not stack思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******
看到别人的解法，真的🐂p，贪心算法
We know that at each point in the string, '( 'count should never be bigger than ')' count, and in the end the difference of two counts should be 0.
So we have two boundaries: lowerBond and higherBound, which respectively represents the minimun possible difference and maximum possbile difference, as long as
higherBound is never below 0.
in the end 0 is between lowerBond and higherBound
in the string, when lowerbound is < 0, we make it back to 0.
We know that the string is valid.
beats 100%
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
lower_bound = higher_bound = 0
for c in s:
lower_bound += 1 if c == '(' else -1
higher_bound += 1 if c != ')' else -1
if higher_bound < 0:
return False
lower_bound = max(lower_bound, 0)
return lower_bound == 0