Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita677174

Browse files
committed
20-valid-parentheses.md was solved in _Python, JavaScript_.
1 parentba02f7f commita677174

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+
varisValid=function (s) {
68+
constrightToLeft=newMap([
69+
[')','('],
70+
['}','{'],
71+
[']','['],
72+
])
73+
conststack= []
74+
75+
for (constcharof s) {
76+
if (!rightToLeft.has(char)) {
77+
stack.push(char)
78+
}elseif (stack.length===0||stack.pop()!=rightToLeft.get(char)) {
79+
returnfalse
80+
}
81+
}
82+
83+
returnstack.length===0
84+
};
85+
```
86+
87+
##Python
88+
```python
89+
classSolution:
90+
defisValid(self,s:str) ->bool:
91+
right_to_left= {
92+
')':'(',
93+
'}':'{',
94+
']':'[',
95+
}
96+
stack= []
97+
98+
for charin s:
99+
if charnotin right_to_left:
100+
stack.append(char)
101+
elifnot stackor stack.pop()!= right_to_left[char]:
102+
returnFalse
103+
104+
returnnot 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+
varisValid=function (s) {
68+
constrightToLeft=newMap([
69+
[')','('],
70+
['}','{'],
71+
[']','['],
72+
])
73+
conststack= []
74+
75+
for (constcharof s) {
76+
if (!rightToLeft.has(char)) {
77+
stack.push(char)
78+
}elseif (stack.length===0||stack.pop()!=rightToLeft.get(char)) {
79+
returnfalse
80+
}
81+
}
82+
83+
returnstack.length===0
84+
};
85+
```
86+
87+
##Python
88+
```python
89+
classSolution:
90+
defisValid(self,s:str) ->bool:
91+
right_to_left= {
92+
')':'(',
93+
'}':'{',
94+
']':'[',
95+
}
96+
stack= []
97+
98+
for charin s:
99+
if charnotin right_to_left:
100+
stack.append(char)
101+
elifnot stackor stack.pop()!= right_to_left[char]:
102+
returnFalse
103+
104+
returnnot 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)
[8]ページ先頭
©2009-2025 Movatter.jp