> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/05_stack_queue/20.-valid-parentheses.md).

# 20. Valid Parentheses

<https://leetcode.com/problems/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](/mle-interview/01_leetcode/07_dfs/301.-remove-invalid-parentheses.md)

[1249. Minimum Remove to Make Valid Parentheses](/mle-interview/01_leetcode/05_stack_queue/1249.-minimum-remove-to-make-valid-parentheses.md)

[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](/mle-interview/01_leetcode/09_dynamic_program/32.-longest-valid-parentheses.md)

[22 Generate Parentheses](/mle-interview/01_leetcode/07_dfs/22.-generate-parentheses.md)

[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
```