力扣00020.有效的括号

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟
有效的括号、栈、字符串、简单

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

提示：

  • $1 <= s.length <= 10^4$
  • s 仅由括号 ‘()[]{}’ 组成

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isValid(string s) {
        stack<char> stack;
        unordered_map<char, char> mapping = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        for (char& c : s) {
            if (mapping.find(c) != mapping.end()) {
                char top_element = stack.empty() ? '#' : stack.top();
                stack.pop();
                if (top_element != mapping[c]) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.empty();
    }
};

结果

执行用时 : 4 ms, 击败 34.94% 使用 C++ 的用户

内存消耗 : 6.66 MB, 击败 20.29% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put(']', '[');
        mapping.put('}', '{');
        for (char c : s.toCharArray()) {
            if (mapping.containsKey(c)) {
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if (topElement != mapping.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

结果

执行用时 : 2 ms, 击败 51.90% 使用 Java 的用户

内存消耗 : 40.38 MB, 击败 15.69% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def isValid(self, s):
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}
        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

结果

执行用时 : 24 ms, 击败 28.80% 使用 Python 的用户

内存消耗 : 13.06 MB, 击败 58.31% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}
        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

结果

执行用时 : 32 ms, 击败 97.63% 使用 Python3 的用户

内存消耗 : 16.83 MB, 击败 16.72% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isValid(char* s) {
    int len = strlen(s);
    char stack[len];
    int top = -1;
    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            stack[++top] = s[i];
        } else {
            if (top == -1) {
                return false;
            }
            char temp = stack[top--];
            if ((s[i] == ')' && temp != '(') || (s[i] == ']' && temp != '[') || (s[i] == '}' && temp != '{')) {
                return false;
            }
        }
    }
    return top == -1;
}

结果

执行用时 : 4 ms, 击败 41.72% 使用 C 的用户

内存消耗 : 6.13 MB, 击败 89.19% 使用 C 的用户

C#

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) {
        if (string.IsNullOrEmpty(s)) return true;
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> mapping = new Dictionary<char, char> {{')', '('}, {']', '['}, {'}', '{'}};
        foreach (char c in s) {
            if (mapping.ContainsValue(c)) {
                stack.Push(c);
            } else if (mapping.TryGetValue(c, out char value)) {
                if (stack.Count == 0 || stack.Pop() != value) {
                    return false;
                }
            }
        }
        return stack.Count == 0;
    }
}

结果

执行用时 : 56 ms, 击败 95.95% 使用 C# 的用户

内存消耗 : 38.44 MB, 击败 12.55% 使用 C# 的用户

JavaScript

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) {
    if (s.length === 0) return true;
    const stack = [];
    const mapping = {')': '(', ']': '[', '}': '{'};
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (mapping[char] !== undefined) {
            const topElement = stack.length === 0 ? '#' : stack.pop();
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
};

结果

执行用时 : 64 ms, 击败 71.45% 使用 JavaScript 的用户

内存消耗 : 48.31 MB, 击败 12.49% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function isValid(s: string): boolean {
    if (s.length === 0) return true;
    const stack: string[] = [];
    const mapping: { [key: string]: string } = {')': '(', ']': '[', '}': '{'};
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (mapping[char] !== undefined) {
            const topElement = stack.length === 0 ? '#' : stack.pop()!;
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}

结果

执行用时 : 68 ms, 击败 64.87% 使用 TypeScript 的用户

内存消耗 : 51.40 MB, 击败 6.85% 使用 TypeScript 的用户

PHP

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
class Solution {
    
    /**
     * @param String $s
     * @return Boolean
     */

    function isValid($s) {
        if (empty($s)) return true;
        $stack = [];
        $mapping = [')' => '(', ']' => '[', '}' => '{'];
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (array_key_exists($char, $mapping)) {
                $topElement = empty($stack) ? '#' : array_pop($stack);
                if ($mapping[$char] !== $topElement) {
                    return false;
                }
            } else {
                array_push($stack, $char);
            }
        }
        return empty($stack);
    }
}

结果

执行用时 : 8 ms, 击败 63.54% 使用 PHP 的用户

内存消耗 : 19.52 MB, 击败 6.25% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func isValid(_ s: String) -> Bool {
        if s.isEmpty {
            return true
        }
        var stack = [Character]()
        let mapping: [Character: Character] = [")": "(", "]": "[", "}": "{"]
        for char in s {
            if let leftBracket = mapping[char] {
                if stack.isEmpty || stack.popLast() != leftBracket {
                    return false
                }
            } else {
                stack.append(char)
            }
        }
        return stack.isEmpty
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 15.52 MB, 击败 5.91% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    fun isValid(s: String): Boolean {
        if (s.isEmpty()) {
            return true
        }
        val stack = Stack<Char>()
        val mapping = mapOf(')' to '(', ']' to '[', '}' to '{')
        for (char in s) {
            if (mapping.containsKey(char)) {
                val topElement = if (stack.isEmpty()) '#' else stack.pop()
                if (mapping[char] != topElement) {
                    return false
                }
            } else {
                stack.push(char)
            }
        }
        return stack.isEmpty()
    }
}

结果

执行用时 : 148 ms, 击败 66.67% 使用 Kotlin 的用户

内存消耗 : 33.78 MB, 击败 44.17% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  bool isValid(String s) {
    if (s.isEmpty) return true;
    final Map<String, String> mapping = {')': '(', ']': '[', '}': '{'};
    final List<String> stack = [];
    for (int i = 0; i < s.length; i++) {
      String char = s[i];
      if (mapping.containsKey(char)) {
        String topElement = stack.isEmpty ? '#' : stack.removeLast();
        if (mapping[char] != topElement) {
          return false;
        }
      } else {
        stack.add(char);
      }
    }
    return stack.isEmpty;
  }
}

结果

执行用时 : 256 ms, 击败 85.71% 使用 Dart 的用户

内存消耗 : 147.11 MB, 击败 100.00% 使用 Dart 的用户

Go

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
func isValid(s string) bool {
    if len(s) == 0 {
        return true
    }
    mapping := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []rune{}
    for _, char := range s {
        if val, ok := mapping[char]; ok {
            var topElement rune
            if len(stack) == 0 {
                topElement = '#'
            } else {
                topElement, stack = stack[len(stack)-1], stack[:len(stack)-1]
            }
            if val != topElement {
                return false
            }
        } else {
            stack = append(stack, char)
        }
    }
    return len(stack) == 0
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 1.93 MB, 击败 16.11% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# @param {String} s
# @return {Boolean}
def is_valid(s)
    return true if s.empty?
    mapping = { ')' => '(', ']' => '[', '}' => '{' }
    stack = []
    s.each_char do |char|
        if mapping.key?(char)
            top_element = stack.empty? ? '#' : stack.pop
            return false if mapping[char] != top_element
        else
            stack.push(char)
        end
    end
    stack.empty?
end

结果

执行用时 : 80 ms, 击败 16.67% 使用 Ruby 的用户

内存消耗 : 206.79 MB, 击败 8.33% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import scala.collection.mutable.Stack

object Solution {
  def isValid(s: String): Boolean = {
    if (s.isEmpty) return true
    val mapping = Map(')' -> '(', ']' -> '[', '}' -> '{')
    val stack = Stack[Char]()
    for (char <- s) {
      if (mapping.contains(char)) {
        val topElement = if (stack.isEmpty) '#' else stack.pop()
        if (mapping(char) != topElement) {
          return false
        }
      } else {
        stack.push(char)
      }
    }
    stack.isEmpty
  }
}

结果

执行用时 : 492 ms, 击败 28.00% 使用 Scala 的用户

内存消耗 : 55.64 MB, 击败 84.00% 使用 Scala 的用户

Rust

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
impl Solution {
    pub fn is_valid(s: String) -> bool {
        if s.is_empty() {
            return true;
        }
        let mut stack = Vec::new();
        let mapping: Vec<(char, char)> = vec![('(', ')'), ('[', ']'), ('{', '}')];
        for c in s.chars() {
            match c {
                '(' | '[' | '{' => stack.push(c),
                _ => {
                    if let Some(&top) = stack.last() {
                        if let Some(&(_, close)) = mapping.iter().find(|&&(open, _)| open == top) {
                            if close == c {
                                stack.pop();
                            } else {
                                return false;
                            }
                        } else {
                            return false;
                        }
                    } else {
                        return false;
                    }
                }
            }
        }
        stack.is_empty()
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.03 MB, 击败 65.16% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
(define/contract (is-valid s)
  (-> string? boolean?)
  (if (string=? s "") #t
      (let loop ((s (string->list s)) (stack '()))
        (cond
          ((null? s) (null? stack))
          ((member (car s) '(#\( #\[ #\{)) (loop (cdr s) (cons (car s) stack)))
          ((and (member (car s) '(#\) #\] #\})) (not (null? stack)) (char=? (car s)
                                                                               (cond ((char=? (car stack) #\() #\))
                                                                                     ((char=? (car stack) #\[) #\])
                                                                                     ((char=? (car stack) #\{) #\})))
                                                 (loop (cdr s) (cdr stack))))
          (else #f)))))

结果

执行用时 : 188 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 98.05 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户