leetcode-20-Valid-Parentheses

描述


Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

分析


这道题目,,,我见过的,,,
这类题目基本上就是用栈的思路吧,首先入栈的当然不能是')','}',']',之后凡是入栈的括号,如果是左括号直接入栈,不是左括号,判断是否与栈顶匹配,不匹配就是false,匹配就消除这一对,最后要做一下判断,如果最后的栈中还有元素(左括号),那么也不是valid。

解决方案1(Python)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False

pairs = {
")": "(",
"]": "[",
"}": "{",
}
stack = list()

for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack

解决方案2(C++)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
bool isValid(string s) {
stack<char> charStack;

for(int i = 0; i < s.length(); i++) {
char nowChar = s[i];
if(nowChar != ')' && nowChar != ']' && nowChar != '}') {
charStack.push(nowChar);
}else {
if(charStack.size() == 0) {
return false;
}

char preChar = charStack.top();
switch(nowChar) {
case ')':
if(preChar == '(') {
charStack.pop();
}else {
return false;
}
break;
case ']':
if(preChar == '[') {
charStack.pop();
}else {
return false;
}
break;
case '}':
if(preChar == '{') {
charStack.pop();
}else {
return false;
}
break;
}
}
}
if(charStack.size() == 0) {
return true;
}else {
return false;
}
}
};

解决方案3(Rust)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
pub fn is_valid(s: String) -> bool {
let mut stack: Vec<char> = Vec::new();
for ch in s.chars().into_iter() {
match stack.last() {
None => {}
Some(&last) => {
if Solution::pair(last, ch) {
stack.pop();
continue
}
}
}
stack.push(ch);
}
stack.is_empty()
}

#[inline(always)]
fn pair(left: char, close: char) -> bool {
(left == '{' && close == '}') || (left == '(' && close == ')') || (left == '[' && close == ']')
}
}

解决方案4(Golang)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func isValid(s string) bool {
if s == "" {
return true
}

var stack []uint8

parenthesesMap := map[uint8]uint8 {
'}': '{',
')': '(',
']': '[',
}

for i := 0; i < len(s); i++ {
if s[i] == '{' || s[i] == '[' || s[i] == '(' {
stack = append(stack, s[i])
} else {
if len(stack) == 0 {
return false
}
if parenthesesMap[s[i]] != stack[len(stack)-1] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}

相关问题


题目来源