Skip to content

Commit a677174

Browse files
gazeldxgazeldx
committed
20-valid-parentheses.md was solved in _Python, JavaScript_.
1 parent ba02f7f commit a677174

File tree

3 files changed

+271
-0
lines changed

3 files changed

+271
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@ You can skip the more difficult problems and do them later.
4848
- [18. 4Sum](en/1-1000/18-4sum.md) was solved in _Python_.
4949

5050
# Stack
51+
- [20. Valid Parentheses](en/1-1000/20-valid-parentheses.md) was solved in _Python, JavaScript_.
5152
- [232. Implement Queue using Stacks](en/1-1000/232-implement-queue-using-stacks.md) was solved in _Python, JavaScript_.
5253

5354
# Queue

‎en/1-1000/20-valid-parentheses.md

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
# 20. Valid Parentheses - LeetCode Solution Best Practice
2+
LeetCode link: [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses), difficulty: **Easy**
3+
4+
## Description of "20. Valid Parentheses"
5+
Given a string `s` containing just the characters `(`, `)`, `{`, `}`, `[` and `]`, determine if the input string is valid.
6+
7+
An input string is valid if:
8+
9+
1. Open brackets must be closed by the same type of brackets.
10+
2. Open brackets must be closed in the correct order.
11+
3. Every close bracket has a corresponding open bracket of the same type.
12+
13+
### [Example 1]
14+
**Input**: `s = "()"`
15+
16+
**Output**: `true`
17+
18+
### [Example 2]
19+
**Input**: `s = "()[]{}"`
20+
21+
**Output**: `true`
22+
23+
### [Example 3]
24+
**Input**: `s = "(]"`
25+
26+
**Output**: `false`
27+
28+
### [Example 4]
29+
**Input**: `s = "([])"`
30+
31+
**Output**: `true`
32+
33+
### [Constraints]
34+
- `1 <= s.length <= 10000`
35+
- `s` consists of parentheses only `()[]{}`.
36+
37+
### Hints
38+
<details>
39+
<summary>Hint 1</summary>
40+
Use a stack of characters.
41+
</details>
42+
43+
<details>
44+
<summary>Hint 2</summary>
45+
When you encounter an opening bracket, push it to the top of the stack.
46+
</details>
47+
48+
<details>
49+
<summary>Hint 3</summary>
50+
When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.
51+
</details>
52+
53+
## Intuition
54+
1. Bracket matching focuses on the `previous character` and the `current character`. There are two situations to consider:
55+
1. If the `current character` is a left bracket, there is no need to match it and it can be saved directly.
56+
2. If the `current character` is a right bracket, and the `previous character` and the `current character` are paired, both characters can disappear; otherwise, if the pairing fails, `false` is returned directly.
57+
2. This scenario that focuses on the `previous character` and the `current character` is suitable for implementation with a `stack`.
58+
3. The mapping relationship between left and right brackets can be saved in a `Map`.
59+
4. Finally, if the stack is empty, it means that all pairings are successful and `true` is returned; otherwise, `false` is returned.
60+
61+
## Complexity
62+
* Time: `O(N)`.
63+
* Space: `O(N)`.
64+
65+
## JavaScript
66+
```javascript
67+
var isValid = function (s) {
68+
const rightToLeft = new Map([
69+
[')', '('],
70+
['}', '{'],
71+
[']', '['],
72+
])
73+
const stack = []
74+
75+
for (const char of s) {
76+
if (!rightToLeft.has(char)) {
77+
stack.push(char)
78+
} else if (stack.length === 0 || stack.pop() != rightToLeft.get(char)) {
79+
return false
80+
}
81+
}
82+
83+
return stack.length === 0
84+
};
85+
```
86+
87+
## Python
88+
```python
89+
class Solution:
90+
def isValid(self, s: str) -> bool:
91+
right_to_left = {
92+
')': '(',
93+
'}': '{',
94+
']': '[',
95+
}
96+
stack = []
97+
98+
for char in s:
99+
if char not in right_to_left:
100+
stack.append(char)
101+
elif not stack or stack.pop() != right_to_left[char]:
102+
return False
103+
104+
return not stack
105+
```
106+
107+
## Java
108+
```java
109+
// Welcome to create a PR to complete the code of this language, thanks!
110+
```
111+
112+
## C++
113+
```cpp
114+
// Welcome to create a PR to complete the code of this language, thanks!
115+
```
116+
117+
## C#
118+
```c#
119+
// Welcome to create a PR to complete the code of this language, thanks!
120+
```
121+
122+
## Go
123+
```go
124+
// Welcome to create a PR to complete the code of this language, thanks!
125+
```
126+
127+
## Ruby
128+
```ruby
129+
# Welcome to create a PR to complete the code of this language, thanks!
130+
```
131+
132+
## C, Kotlin, Swift, Rust or other languages
133+
```
134+
// Welcome to create a PR to complete the code of this language, thanks!
135+
```

‎zh/1-1000/20-valid-parentheses.md

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
# 20. 有效的括号 - 力扣题解最佳实践
2+
力扣链接：[20. 有效的括号](https://leetcode.cn/problems/valid-parentheses), 难度: **简单**。
3+
4+
## 力扣“20. 有效的括号”问题描述
5+
给定一个只包括 `(`，`)`，`{`，`}`，`[`，`]` 的字符串 `s` ，判断字符串是否有效。
6+
7+
有效字符串需满足：
8+
9+
1. 左括号必须用相同类型的右括号闭合。
10+
2. 左括号必须以正确的顺序闭合。
11+
3. 每个右括号都有一个对应的相同类型的左括号。
12+
13+
### [示例 1]
14+
**输入**: `s = "()"`
15+
16+
**输出**: `true`
17+
18+
### [示例 2]
19+
**输入**: `s = "()[]{}"`
20+
21+
**输出**: `true`
22+
23+
### [示例 3]
24+
**输入**: `s = "(]"`
25+
26+
**输出**: `false`
27+
28+
### [示例 4]
29+
**输入**: `s = "([])"`
30+
31+
**输出**: `true`
32+
33+
### [约束]
34+
- `1 <= s.length <= 10000`
35+
- `s` 仅由括号 `()[]{}` 组成
36+
37+
### 提示
38+
<details>
39+
<summary>提示 1</summary>
40+
Use a stack of characters.
41+
</details>
42+
43+
<details>
44+
<summary>提示 2</summary>
45+
When you encounter an opening bracket, push it to the top of the stack.
46+
</details>
47+
48+
<details>
49+
<summary>提示 3</summary>
50+
When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.
51+
</details>
52+
53+
## 思路
54+
1. 括号匹配关注的主要是`前一个字符`与`当前字符`。有两种情况要考虑：
55+
1. 如果`当前字符`是左括号，则不需要匹配，直接保存起来。
56+
2. 如果`当前字符`是右括号，并且`前一个字符`与`当前字符`配成了一对，则这两个字符都可以**消失**了；反之，如果配对失败，直接返回`false`。
57+
2. 这种关注`前一个字符`与`当前字符`的场景，适合用`栈`实现。
58+
3. 左右括号之间的对应关系可以保存在一个`Map`中。
59+
4. 最后，如果栈为空，说明全部配对成功，返回`true`；否则返回`false`。
60+
61+
## 复杂度
62+
* 时间：`O(N)`。
63+
* 空间：`O(N)`。
64+
65+
## JavaScript
66+
```javascript
67+
var isValid = function (s) {
68+
const rightToLeft = new Map([
69+
[')', '('],
70+
['}', '{'],
71+
[']', '['],
72+
])
73+
const stack = []
74+
75+
for (const char of s) {
76+
if (!rightToLeft.has(char)) {
77+
stack.push(char)
78+
} else if (stack.length === 0 || stack.pop() != rightToLeft.get(char)) {
79+
return false
80+
}
81+
}
82+
83+
return stack.length === 0
84+
};
85+
```
86+
87+
## Python
88+
```python
89+
class Solution:
90+
def isValid(self, s: str) -> bool:
91+
right_to_left = {
92+
')': '(',
93+
'}': '{',
94+
']': '[',
95+
}
96+
stack = []
97+
98+
for char in s:
99+
if char not in right_to_left:
100+
stack.append(char)
101+
elif not stack or stack.pop() != right_to_left[char]:
102+
return False
103+
104+
return not stack
105+
```
106+
107+
## Java
108+
```java
109+
// Welcome to create a PR to complete the code of this language, thanks!
110+
```
111+
112+
## C++
113+
```cpp
114+
// Welcome to create a PR to complete the code of this language, thanks!
115+
```
116+
117+
## C#
118+
```c#
119+
// Welcome to create a PR to complete the code of this language, thanks!
120+
```
121+
122+
## Go
123+
```go
124+
// Welcome to create a PR to complete the code of this language, thanks!
125+
```
126+
127+
## Ruby
128+
```ruby
129+
# Welcome to create a PR to complete the code of this language, thanks!
130+
```
131+
132+
## C, Kotlin, Swift, Rust or other languages
133+
```
134+
// Welcome to create a PR to complete the code of this language, thanks!
135+
```

0 commit comments

Comments
 (0)