Description#
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104s consists of parentheses only '()[]{}'.
Solutions#
Solution 1: Stack#
Traverse the bracket string $s$. When encountering a left bracket, push the current left bracket into the stack; when encountering a right bracket, pop the top element of the stack (if the stack is empty, directly return false), and judge whether it matches. If it does not match, directly return false.
Alternatively, when encountering a left bracket, you can push the corresponding right bracket into the stack; when encountering a right bracket, pop the top element of the stack (if the stack is empty, directly return false), and judge whether they are equal. If they do not match, directly return false.
The difference between the two methods is only the timing of bracket conversion, one is when pushing into the stack, and the other is when popping out of the stack.
At the end of the traversal, if the stack is empty, it means the bracket string is valid, return true; otherwise, return false.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the bracket string $s$.
1
2
3
4
5
6
7
8
9
10
| class Solution:
def isValid(self, s: str) -> bool:
stk = []
d = {'()', '[]', '{}'}
for c in s:
if c in '({[':
stk.append(c)
elif not stk or stk.pop() + c not in d:
return False
return not stk
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean isValid(String s) {
Deque<Character> stk = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stk.push(c);
} else if (stk.isEmpty() || !match(stk.pop(), c)) {
return false;
}
}
return stk.isEmpty();
}
private boolean match(char l, char r) {
return (l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']');
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
bool isValid(string s) {
string stk;
for (char c : s) {
if (c == '(' || c == '{' || c == '[')
stk.push_back(c);
else if (stk.empty() || !match(stk.back(), c))
return false;
else
stk.pop_back();
}
return stk.empty();
}
bool match(char l, char r) {
return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func isValid(s string) bool {
stk := []rune{}
for _, c := range s {
if c == '(' || c == '{' || c == '[' {
stk = append(stk, c)
} else if len(stk) == 0 || !match(stk[len(stk)-1], c) {
return false
} else {
stk = stk[:len(stk)-1]
}
}
return len(stk) == 0
}
func match(l, r rune) bool {
return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}')
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| const map = new Map([
['(', ')'],
['[', ']'],
['{', '}'],
]);
function isValid(s: string): boolean {
const stack = [];
for (const c of s) {
if (map.has(c)) {
stack.push(map.get(c));
} else if (stack.pop() !== c) {
return false;
}
}
return stack.length === 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| use std::collections::HashMap;
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut map = HashMap::new();
map.insert('(', ')');
map.insert('[', ']');
map.insert('{', '}');
let mut stack = vec![];
for c in s.chars() {
if map.contains_key(&c) {
stack.push(map[&c]);
} else if stack.pop().unwrap_or(' ') != c {
return false;
}
}
stack.len() == 0
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
let stk = [];
for (const c of s) {
if (c == '(' || c == '{' || c == '[') {
stk.push(c);
} else if (stk.length == 0 || !match(stk[stk.length - 1], c)) {
return false;
} else {
stk.pop();
}
}
return stk.length == 0;
};
function match(l, r) {
return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public bool IsValid(string s) {
Stack<char> stk = new Stack<char>();
foreach (var c in s.ToCharArray()) {
if (c == '(') {
stk.Push(')');
} else if (c == '[') {
stk.Push(']');
} else if (c == '{') {
stk.Push('}');
} else if (stk.Count == 0 || stk.Pop() != c) {
return false;
}
}
return stk.Count == 0;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| # @param {String} s
# @return {Boolean}
def is_valid(s)
stack = ''
s.split('').each do |c|
if ['{', '[', '('].include?(c)
stack += c
else
if c == '}' && stack[stack.length - 1] == '{'
stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
elsif c == ']' && stack[stack.length - 1] == '['
stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
elsif c == ')' && stack[stack.length - 1] == '('
stack = stack.length > 1 ? stack[0..stack.length - 2] : ""
else
return false
end
end
end
stack == ''
end
|
