825 字

4 分钟

leetcode算法题-有效的括号

2024-11-11

杂七杂八

算法

/

C#

有效的括号(简单)#

leetcode：https://leetcode.cn/problems/valid-parentheses/description/

前言#

防止脑袋生锈，做一下leetcode的简单算法题，难得也做不来哈哈。

大佬绕道，小白可看。

题目描述#

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

有效字符串需满足：

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

示例 1：

**输入：**s = ”()”

**输出：**true

示例 2：

**输入：**s = ”()[]{}”

**输出：**true

示例 3：

**输入：**s = ”(]”

**输出：**false

示例 4：

**输入：**s = ”([])”

**输出：**true

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

题目解析#

通过题目描述可以举例哪些是有效字符串，哪些是无效字符串，如：

有效字符串

"()"
"({})"
"()[]"

无效字符串

"(]"
"({)}"
")"

不难发现即使字符串中有闭合但是顺序不对也是属于无效字符串。

解题思路#

右括号不一定出现在左括号下一位

"([{}])"

左右括号必须以正确的顺序闭合：

"({})"

"({)}"

字符串中会存在有效的括号对也会有无效的括号对了，如：

"({})({})"

"({})({)}"

尝试将有效的括号对一一消除掉

"()({})" => "({})"=>"()"=>""

"()({)}"=>"({)}"

如果是有效的字符串最终会得到空字符串，反之则是无效字符串。

伪代码#

1
遍历字符串:
2
  如果是左括号:
3
    等待遍历到与之对应的右括号
4
  如果是右括号:
5
    查看是否有与之对应的左括号
6
      如果有，则消除
7
      如果没有，当前字符串无效

动图#

初步总结#

通过前面的解题思路和动图可以发现，最后遍历到的左括号，最先匹配到有效的右括号。

这可以看作为**“后进先出”**的栈。后加入的元素最先被处理。

后进先出的栈#

栈的定义#

栈（Stack）是一种数据结构，遵循后进先出（LIFO, Last In First Out）的原则。也就是说，最后插入栈中的元素最先被取出。栈可以用来存储数据、管理函数调用、实现撤销操作等。

栈的主要操作包括：

压入（Push）：将一个元素添加到栈顶。
弹出（Pop）：移除并返回栈顶的元素。
查看栈顶（Peek/Top）：返回栈顶的元素但不移除它。
检查栈是否为空（IsEmpty）：判断栈中是否还有元素。

开始解题#

图片详解#

1
遍历字符串:
2
  如果是左括号:
3
    入栈
4
  如果是右括号:
5
    查看栈顶元素
6
      如果是对应的左括号则出栈
7
      如果不是，当前字符串无效

代码实现#

1
public bool IsValid(string s) {
2
  Stack<char> stack = new Stack<char>();
3
  foreach (char c in s)
4
  {
5
    switch(c)
6
    {
7
            case '{':
8
            case '[':
9
            case '(':
10
              stack.Push(c);
11
              break;
12
      case '}':
13
        if(stack.Count == 0 || stack.Pop()!= '{')
14
          return false;
15
        break;
16
      case ']':
17
        if(stack.Count == 0 || stack.Pop()!= '[')
18
        return false;
19
        break;
20
      case ')':
21
        if(stack.Count == 0 || stack.Pop()!= '(')
22
          return false;
23
        break;
24
    }
25
  }
26
  return stack.Count == 0;
27
}

复杂度分析#

空间复杂度：O(n)
时间复杂度：O(n)

结果展示#

其他解法#

1
public bool IsValid(string s) {
2
  int length = s.Length/ 2;
3
  for (int i = 0; i < length; i++) {
4
    s = s.Replace("()", "").Replace("{}", "").Replace("[]", "");
5
  }
6
  return s.Length == 0;
7
}

有效的括号(简单)#

前言#

题目描述#

题目解析#

解题思路#

伪代码#

动图#

初步总结#

后进先出的栈#

栈的定义#

开始解题#

图片详解#

代码实现#

复杂度分析#

结果展示#

其他解法#

相关链接#