有效的括号（leetcode 20）

恋喵大鲤鱼

发布于 2022-09-27 21:05:35

3020

文章被收录于专栏：C/C++基础C/C++基础

文章目录

1.问题描述

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入："{[]}"
输出：true

示例 4：

输入：s = "(]"
输出：false

示例 5：

输入：s = "([)]"
输出：false

2.难度等级

easy。

3.热门指数

★★★★☆

出题公司：深圳云摩科技、bilibili。

4.解题思路

捋清什么是有效字符串，那么解题思路便浮出水面。

遍历给定的字符串 s，当遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号与其闭合。在遇到对应的右括号之前，有两种情况：

一种是下一个相邻的就是对应的右括号，如 ()[]{}；
一种是会有其他的括号，那么被包裹的子串也需要是有效字符串，如 ([]{})。

如果不满足上面的要求，就是无效的字符串。

知道了什么是效字符串后，我们会发现其有一个特性，所有成对字符串都可以被 “消除”。如果遍历完后有剩余字符，那么说明其是无效字符串。整个过程有点像玩俄罗斯方块，最后全部被消除说明是有效字符串，反之便是无效字符串。

比如遍历 ([]{})：

(
([
([]  // [] 成对消除后继续遍历
({
({} // {} 成对消除后继续遍历
()  // () 成对消除后遍历完毕

如何实现上面遍历消除的过程呢？因为消除的成对括号都在最右边，所以我们可以使用栈来实现。将遍历左括号入栈，遇到右括号时判断其与栈顶的左括号能否成对，如果成对则将左括号出栈，如果不成对，则直接返回 False。遍历完成后，栈如果是空的则是有效字符串，反之为无效字符串。

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

复杂度分析：

时间复杂度：O(n)，其中 n 是字符串的长度。

空间复杂度：O(n/2)，栈中最多保留全部的左括号。

5.实现示例

5.1 C++

#include <stack>

// isValid 是否为有效字符串。
bool isValid(string s) {
  int n = s.size();
  if (n % 2 == 1) {
    return false;
  }

  stack<char> stk;
  for (char c : s) {
    if (c == '(' || c == '[' || c == '{') {
      stk.push(c);
      continue;
    }
    // 必须有左括号在栈中。
    if (stk.empty()) {
      return false;
    }
    switch (c) {
    case ')':
      if (stk.top() != '(') {
        return false;
      }
      break;
    case ']':
      if (stk.top() != '[') {
        return false;
      }
      break;
    case '}':
      if (stk.top() != '{') {
        return false;
      }
      break;
    }
    stk.pop();
  }
  return stk.empty();
}

5.2 Golang

// isValid 是否为有效字符串。
func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    var stack []rune
    for _, c := range s {
        if c == '(' || c == '[' || c == '{' {
            stack = append(stack, c)
            continue
        }
        // 必须有左括号在栈中。
        if len(stack) == 0 {
            return false
        }
        switch c {
        case ')':
            if stack[len(stack)-1] != '(' {
                return false
            }
        case ']':
            if stack[len(stack)-1] != '[' {
                return false
            }
        case '}':
            if stack[len(stack)-1] != '{' {
                return false
            }
        }
        stack = stack[:len(stack)-1]
    }
    return len(stack) == 0
}