文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / longest-valid-parentheses
文件大小:
1.07 KB
下载地址:
文本预览:
## Counting while [Valid Parentheses](../valid-parentheses)
When a pair of valid parentheses is found, just add `2` to count.
However, the counting method is a bit tricky. Show you using animation
### Animation
This method adds a counting stack.
```
input [ ( ( ) ( ) ) ]
count []
stack []
i
```
No match put `)` and `(` into stack
```
input [ ) ( ) ) ]
count [ 0 0 ]
stack [ ( ( ]
i
```
found matches pop stack and `count[1] = count[1] + 2`
```
input [ ( ) ) ]
count [ 0 2 ]
stack [ ( ]
i
```
just two steps.
found another matches `(` and `)` pop stack and `count[1] = count[1] + 2`
```
input [ ]
count [ 0 4 ]
stack [ ]
i
```
found matches, but, this time, `count[0] = count[0] + 2` is not enough.
It should be `count[0] = count[0] + 2 + count[1]`, because that here `0` matches parentheses indicates that the current parentheses is enclosing the `1..current`.
Generally, when meets a match,
```
count[stack.size()] = count[stack.size()] + 2 + count[stack.size() + 1]
```
then reset the `count[stack.size() + 1]` to `0`.
When a pair of valid parentheses is found, just add `2` to count.
However, the counting method is a bit tricky. Show you using animation
### Animation
This method adds a counting stack.
```
input [ ( ( ) ( ) ) ]
count []
stack []
i
```
No match put `)` and `(` into stack
```
input [ ) ( ) ) ]
count [ 0 0 ]
stack [ ( ( ]
i
```
found matches pop stack and `count[1] = count[1] + 2`
```
input [ ( ) ) ]
count [ 0 2 ]
stack [ ( ]
i
```
just two steps.
found another matches `(` and `)` pop stack and `count[1] = count[1] + 2`
```
input [ ]
count [ 0 4 ]
stack [ ]
i
```
found matches, but, this time, `count[0] = count[0] + 2` is not enough.
It should be `count[0] = count[0] + 2 + count[1]`, because that here `0` matches parentheses indicates that the current parentheses is enclosing the `1..current`.
Generally, when meets a match,
```
count[stack.size()] = count[stack.size()] + 2 + count[stack.size() + 1]
```
then reset the `count[stack.size() + 1]` to `0`.
点赞
回复
X