KK's blog

每天积累多一些

0%

LeetCode 678 Valid Parenthesis String

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>Input: s = "()" Output: true </pre>

Example 2:

<pre>Input: s = "(*)" Output: true </pre>

Example 3:

<pre>Input: s = "(*))" Output: true </pre>

Constraints:

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

</div>

题目大意：

求给定字符串带星号是否合法括号配对。

Stack算法思路(推荐)：

括号题优先考虑用Stack。如果不带星号，回忆合法括号题，有三种不合法情况，此题只需考虑两种，不需考虑多种括号类型 三种不合法情况： '[' (stack有余), ']' (要匹配的时候stack为空)
难点：

  1. 在于要去想多一个栈来存星号，因为星号可以作为左括号备选去match右括号。右括号在两个栈中优先配对左括号，星号可以为空。如果两个栈均为空，处理了第一种不合法情况
  2. 循环后，如果两栈有余，分4中情况讨论：
    1. 左括号栈有余星号栈空，正是第二种不合法情况
    2. 左括号栈空星号栈空，合法
    3. 左括号栈空星号栈有余，合法，星号可为空
    4. 都有余，这是难点二。星号可以作为右括号去配对左括号，前提条件是星号在左括号之后，考虑*(，这是不合法

注意事项：

  1. 如果for循环出来后，两栈不为空，要比较先后顺序
  2. for loop后，L18 - Line 19记得pop，否则死循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def checkValidString(self, s: str) -> bool:
	stack_left, stack_star = [], []
	for i in range(len(s)):
		if s[i] == '(':
			stack_left.append(i)
		if s[i] == '*':
			stack_star.append(i)
		if s[i] == ')':
			if stack_left:  # match ( first rather than * because * can be empty
				stack_left.pop()
			elif stack_star:
				stack_star.pop()
			else:
				return False
	while stack_left and stack_star:  # use * to match (
		if stack_left[-1] > stack_star[-1]:  # consider *(
			return False
		stack_left.pop()
		stack_star.pop()
	return len(stack_left) == 0  # stack_star can be non empty

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

统计算法II解题思路：

括号题另一个常用思路是用统计左右括号数。此题较难想到是用一个左括号数量范围去验证。
lo为左括号的最少合法个数，hi为左括号的最大合法个数，有范围是因为星号可以变成左右括号或空。
遇到左括号，都加1，遇到右括号，都减1，遇到星号，假设星号为右括号，所以lo减1，hi加1.
如果hi小于0，表示最大左括号数小于右括号数，不满足此法的规则一，不合法

难点在于lo设为非负。因为lo是最少且合法，合法意思是lo不是单纯地将所有星号变成右括号，而是当左括号不足时，用提高下限，将星号变成空，体现在令lo为非负。
for循环后，lo必须为0，运用了法则二，左右括号相等。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def checkValidString(self, s: str) -> bool:
	lo = hi = 0
	for char in s:
		if char == '(':
			lo += 1
			hi += 1
		if char == '*':
			if lo > 0:  # treat * as empty space
				lo -= 1
			hi += 1
		if char == ')':
			if lo > 0:  # treat the previous * as empty space
				lo -= 1
			hi -= 1
		if hi < 0:  # the num of right parenthesis > left ones
			return False
	return lo == 0  # the num of right parenthesis should equal to left ones

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

DP算法III解题思路：

基本情况为s[i], s[j] 分别在(*, )* 就合法 如果用单边DP，并不能确定区间内那些合法，所以只能用区间型DP
dp[i][j] = s[i-1] == '*' and dp[i+1][j] 星号不匹配 = s[i-1] in '(*' and dp[i+1][k-1] and s[k-1] in (')*') and dp[k+1][j] 星号匹配

具体参考leetcode答案
DP基本情况比较难想出来且递归是复杂，实现易错，不推荐。不过可以多了解区间型DP的模式

算法分析：

时间复杂度为O(n^3)，空间复杂度O(n^2)

Free mock interview