KK's blog

LeetCode 032 Longest Valid Parentheses

Posted on 2021-12-08 Edited on 2021-12-13 Disqus:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.

Example 2:

Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.

Example 3:

Input: s = “”
Output: 0

Constraints:

`0 <= s.length <= 3 10⁴*s[i]is‘(‘, or‘)’`.

题目大意：

最长括号对数。

Stack算法思路(推荐)：

括号题优先考虑用Stack。由于只有单种括号，只需考虑两种不合法情况。
三种不合法情况： ‘[‘ (stack有余), ‘]’ (要匹配的时候stack为空)
难点： 1. 用下标存于stack，方便计算长度。不合法的保留栈中，这样不合法之间的距离-1就是合法的长度

注意事项：

Stack存了左右括号，不只存左括号，所以Line 7要验证栈顶为左括号
循环后头尾加-1和s长度，方便头尾计算

Python代码：

def longestValidParentheses(self, s: str) -> int:
	stack = []
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		if s[i] == ')':
			if stack and s[stack[-1]] == '(':  # remember
				stack.pop()
			else:
				stack.append(i)

	# ())(()) # ())
	stack.insert(0, -1)
	stack.append(len(s))
	max_len = 0
	while len(stack) > 1:
		index = stack.pop()
		max_len = max(max_len, index - stack[-1] - 1)
	return max_len

算法分析：

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

DP算法II解题思路：

注意事项：

答案用max_len
条件s[i - 1 - dp[i - 1] - 1]和递归式dp[i - dp[i - 1] - 2]不能越界
递归式要加dp[i - dp[i - 1] - 2]，dp[..]”(“dp..[]”)” 就是第一个递归式，容易忽略

Python代码：

# dp[i] = max -> dp[i-2] + 2 if s[i-2:i] == ()
#             -> dp[i-1] + 2 + dp[i-1-dp[i-1]-2] if s[i-1-dp[i-1]-1]== ( and s[i-1] == )
def longestValidParentheses2(self, s: str) -> int:
	dp = [0] * (len(s) + 1)
	max_len = 0  # remember
	for i in range(2, len(dp)):
		dp[i] = max(dp[i], dp[i - 2] + 2 if s[i - 2:i] == '()' else 0)
		prev_dp = 0  # remember
		if i - dp[i - 1] - 2 >= 0:
			prev_dp = dp[i - dp[i - 1] - 2]
		# remember i - 1 - dp[i - 1] - 1 >= 0
		dp[i] = max(dp[i], dp[i - 1] + 2 + prev_dp if i - 1 - dp[i - 1] - 1 >= 0 and s[i - 1 - dp[i - 1] - 1] == '(' and s[i - 1] == ')' else 0)
		max_len = max(max_len, dp[i])
	return max_len

算法分析：

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

统计算法III解题思路：

括号题另一个常用思路是用统计左右括号数。维护四个变量left, right, res, max_len
当左括号小于右括号数（第一个规律）：重设全部变量
当左括号等于右括号数（第二个规律）：满足两个条件，可以计算res。重设left，right，准备计算下一轮res。不重设res，因为可以连续如()()

注意事项：

上述情况只覆盖了()),不能覆盖((), 因为左括号数在每一位永远都不会等于右括号数。所以旋转180度再做一次。

Python代码：

def longestValidParentheses3(self, s: str) -> int:
	max_len = self.get_max_len(s)
	res = []
	PARENTHESES_DICT = {'(': ')', ')': '('}
	for char in s:
		res.append(PARENTHESES_DICT[char])
	max_len = max(max_len, self.get_max_len(res[::-1]))
	return max_len

def get_max_len(self, s: str) -> int:
	max_len = res = left = right = 0
	for char in s:
		if char == '(':
			left += 1
		if char == ')':
			right += 1
			if left < right:
				left = 0
				right = 0
				res = 0
			if left == right:  # (())), ()()
				res += left * 2
				max_len = max(max_len, res)
				left = 0
				right = 0
	return max_len

算法分析：

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

LeetCode 678 Valid Parenthesis String

Posted on 2021-12-08 Edited on 2021-12-13 Disqus:

LeetCode

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 '*'.

题目大意：

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

Stack算法思路(推荐)：

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

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

注意事项：

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

Python代码：

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代码：

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)

括号题或者字符串运算题

Posted on 2021-12-07 Edited on 2021-12-19 Disqus:

括号题

算法思路：

优先考虑用Stack。Stack可以将字符压入比较或者字符的下标压入比较，后者信息量更大
三种情况不合法： ‘[‘ (stack有余，for后发生), ‘]’ (要匹配的时候stack为空，for中发生), ‘{]’ (不匹配，for中发生)
DP
1) 左括号的数量在每一位都大于等于右括号数量
2) 右括号的总和要等于右括号总和
以上两个条件都满足的话，左右括号匹配，但此法只能用于单种括号

应用：

括号题
字符串运算题如, 3+4, (3+4)*5

括号运算题

res是作为同一层的临时计算结果，若遇到左括号，res保留在stack中且reset，若遇到右括号，stack的结果还原到res
num也是临时变量负责储存整数

注意事项：

char.isdigit()的计算
左括号：入栈和reset res和num。
右括号:出栈和还原res = tmp + f(res)。

括号运算题模板：

def parenthesis(self, s: str) -> int:
    (Optional) s边界处理如s += '+' 
	res, num, stack = '', 0, []
	for char in s:
        if char == ' ':
            continue
		if char.isdigit(): 
			num = num * 10 + int(char)
		if char.isalpha():
			res += char
		if char == '+' # 或其他操作符
			res = 同层计算
			num = 0  # reset 不能reset res，因为res是这一层的临时结果
		if char == '[':
			多个入栈(res) 
			res = '' # reset
			num = 0  # reset 
		if char == ']':
			(Optional) res = 同层计算, 这两步同+运算符
			tmp = 多个出栈
			res = tmp + f(res) # 还原上层结果
			(Optional) num = 0
	return res

算法分析：

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

LeetCode 1249 Minimum Remove to Make Valid Parentheses

Posted on 2021-12-07 Edited on 2022-03-16 Disqus:

LeetCode

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

Example 2:

Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:

Input: s = “))((“
Output: “”
Explanation: An empty string is also valid.

Example 4:

Input: s = “(a(b(c)d)”
Output: “a(b(c)d)”

Constraints: 1 <= s.length <= 10<sup>5</sup>
* s[i] is either'(' , ')', or lowercase English letter.

题目大意：

去掉最小不合法括号数剩下的字符串。

Stack算法思路：

括号题优先考虑用Stack。此题将下标存于stack中，stack留下的是不合法括号下标，也就是需要删除的

LeetCode 1249 Minimum Remove to Make Valid Parentheses 求一个最优解 Medium, Stack
LeetCode 921 Minimum Add to Make Parentheses Valid 求一个最优解 Medium, Stack
LeetCode 301 Remove Invalid Parentheses 求所有最优解 Hard，此题答案包含上题, BFS

注意事项：

当括号配对时才出栈 Line 6

Python代码：

def minRemoveToMakeValid(self, s: str) -> str:
	stack, res = [], ''
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif stack and s[stack[-1]] == '(' and s[i] == ')':  # remember
			stack.pop()
		elif s[i] == ')':
			stack.append(i)
	for i in range(len(s)):
		if i in set(stack):
			continue
		res += s[i]
	return res

算法分析：

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

LeetCode 020 Valid Parentheses

Posted on 2021-12-06 Edited on 2021-12-13 Disqus:

LeetCode

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

Input: s = “()”
Output: true

Example 2:

Input: s = “()[]{}”
Output: true

Example 3:

Input: s = “(]”
Output: false

Example 4:

Input: s = “([)]”
Output: false

Example 5:

Input: s = “{[]}”
Output: true

Constraints:

1 <= s.length <= 10<sup>4</sup> s consists of parentheses only '()[]{}'.

题目大意：

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

算法思路：

括号题优先考虑用Stack

注意事项：

三种不合法情况： ‘[‘ (stack有余), ‘]’ (要匹配的时候stack为空), ‘{]’ (不匹配)

Python代码：

PARENTHESES_DICT = {'(': ')', '[': ']', '{': '}'}
class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return False
        stack = []
        for char in s:
            if char in '([{':
                stack.append(char)
            else:
                if not stack:
                    return False
                left = stack.pop()
                if PARENTHESES_DICT[left] != char:
                    return False
        return True if not stack else False

算法分析：

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