# 20. Valid Parentheses
## solution
* 括号合理: 任一位置，左括号数量大于等于右括号数量；最后位置，左等于右
```python
class Solution:
def isValid(self, s: str) -> bool:
anchor = {
")": "(",
"]": "[",
"}": "{"
}
stack = []
for sub in s:
if sub in ['(', '[', '{']:
stack.append(sub)
else:
if not stack or anchor[sub] != stack.pop(-1):
return False
else:
continue
if not stack:
return True
else:
return False
```
时间复杂度：O()\
空间复杂度：O()
## follow up-括号类
[241. Different Ways to Add Parentheses](https://leetcode.com/problems/different-ways-to-add-parentheses/description/)
```python
class Solution:
def diffWaysToCompute(self, expression: str) -> List[int]:
# 每次遇到符号，对左右分而治之
if expression.isdigit():
return [int(expression)] # 对结果进行循环，返回的是list
res = []
for i in range(len(expression)):
if expression[i] in "-+*":
left = self.diffWaysToCompute(expression[:i])
right = self.diffWaysToCompute(expression[i+1:])
for l in left:
for r in right:
if expression[i] == '+':
res.append(l+r)
elif expression[i] == '-':
res.append(l-r)
elif expression[i] == '*':
res.append(l*r)
return res
```
```python
class Solution(object):
def diffWaysToCompute(self, input):
m = {}
return self.dfs(input, m)
def dfs(self, input, m):
if input in m:
return m[input]
if input.isdigit():
m[input] = int(input)
return [int(input)]
ret = []
for i, c in enumerate(input):
if c in "+-*":
l = self.diffWaysToCompute(input[:i])
r = self.diffWaysToCompute(input[i+1:])
ret.extend(eval(str(x)+c+str(y)) for x in l for y in r)
m[input] = ret
return ret
```
[282. Expression Add Operators](https://leetcode.com/problems/expression-add-operators/description/)
```python
# for循环尝试在每个位置增加运算符, 得到一层结果后续递归添加后续的运算符.
```
[301 Remove Invalid Parentheses](https://longxingtan.gitbook.io/mle-interview/01_leetcode/07_dfs/301.-remove-invalid-parentheses)
[1249. Minimum Remove to Make Valid Parentheses](https://longxingtan.gitbook.io/mle-interview/01_leetcode/05_stack_queue/1249.-minimum-remove-to-make-valid-parentheses)
[921. Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/)
```python
# 与1249镜像题目, one-pass, 只有左括号入栈.
# 可以进一步优化空间O(1), 不使用栈
class Solution:
def minAddToMakeValid(self, s: str) -> int:
res = 0
stack = []
s = list(s) # 转化为list
for i, char in enumerate(s):
if char == '(':
stack.append(i) # 入栈参数无所谓
elif char == ')':
if stack:
stack.pop()
else:
res += 1
while stack:
stack.pop()
res += 1
return res
```
[32. Longest Valid Parentheses](https://longxingtan.gitbook.io/mle-interview/01_leetcode/09_dynamic_program/32.-longest-valid-parentheses)
[22 Generate Parentheses](https://longxingtan.gitbook.io/mle-interview/01_leetcode/07_dfs/22.-generate-parentheses)
[636. Exclusive Time of Functions](https://leetcode.com/problems/exclusive-time-of-functions/description/)
```python
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res_dict = [0] * n
prev_time = 0 # 定义一个时间对解决问题很关键
history = []
for log in logs:
id, status, start_time = log.split(':')
# 最好一开始就把start_time转为int
id = int(id)
start_time = int(start_time)
if status == 'start':
if history:
# 此时不能pop，但需要加一段完成时间
res_dict[history[-1]] += start_time - prev_time
history.append(id)
# 注意, 2开始, 意味着上一个1结束; 5结束, 意味着下一个6开始
prev_time = start_time
else:
history.pop()
res_dict[id] += start_time - prev_time + 1
prev_time = start_time + 1
return res_dict
```
```python
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
mydict = collections.defaultdict(int)
current = 0
stack = []
for log in logs:
id, status, time = log.split(':')
time = int(time)
id = int(id)
if status == 'start':
if stack:
mydict[stack[-1]] += int(time) - int(current)
stack.append(id)
current = time
else:
stack.pop()
mydict[id] += int(time) - int(current) + 1
current = time + 1
# 如果id不转化为int的话，就会因为按照字母排序把10排在2前面而出现问题
return [mydict[i] for i in sorted(mydict)]
```
multi thread版本
* 改成一个hashmap of stacks, key=thread\_id, value=stack of events and timestamps, reduce到同一个function
[591. Tag Validator](https://leetcode.com/problems/tag-validator/description/)
```python
```
[678. Valid Parenthesis String](https://leetcode.com/problems/valid-parenthesis-string/description/)
```python
class Solution:
def checkValidString(self, s: str) -> bool:
stack = []
star = []
for index, char in enumerate(s):
if char == '(':
stack.append(index)
elif char == ')':
if stack:
stack.pop()
elif star:
star.pop()
else:
return False
else:
star.append(index)
while stack:
if star and stack[-1] < star[-1]:
stack.pop()
star.pop()
else:
return False
return True
```
* 错误方案, 想通过大小比较。相当于中间漏掉了每一个\*的具体变换，有的case不通过
```python
class Solution:
def checkValidString(self, s: str) -> bool:
counter = collections.defaultdict(int)
for char in s:
counter[char] += 1
if counter['('] + counter['*'] < counter[')']:
return False
if counter['('] > counter['*'] + counter[')'] or counter[')'] > counter['*'] + counter['(']:
return False
return True
```
[1541. Minimum Insertions to Balance a Parentheses String](https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/description/)
```python
class Solution:
def minInsertions(self, s: str) -> int:
num_left = 0
res = 0
i = 0
while i < len(s):
if s[i] == '(':
num_left += 1
else:
if num_left > 0:
num_left -= 1
else:
res += 1
if i < len(s) - 1 and s[i+1] == ')':
i += 1
else:
res += 1
i += 1
return res + num_left * 2
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/05_stack_queue/20.-valid-parentheses.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.