[数据结构与算法]有效的括号（判断括号是否匹配），栈，字典

Bertha 。 2022-12-06 04:17 124阅读 0赞

var isValid = function (s) { 
                if (s.length % 2 === 1) { 
                    //如果字符串是奇数，则括号必定无法一一匹配
                    return false
                }
                const stack = [];
                for (let i = 0; i < s.length; i++) { 
                    const c = s[i]
                    if (c === '(' || c === '[' || c === '{') { 
                        stack.push(c)
                    } else { 
                        const t = stack[stack.length - 1]
                        if (
                            (t === '(' && c === ')') ||
                            (t === '[' && c === ']') ||
                            (t === '{' && c === '}')
                        ) { 
                            stack.pop()
                        } else { 
                            return false
                        }
                    }
                }
                // 栈空则表示匹配，栈不空则表示不匹配
                return stack.length === 0
            }

**时间复杂度:O(n)** :

遍历s字符串一次，s.length次循环

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

最差情况全是左括号，则要把s.length个字符push进入stack

**用字典优化：**

var isValid = function (s) { 
                if (s.length % 2 === 1) { 
                    //如果字符串是奇数，则括号必定无法一一匹配
                    return false
                }
                const stack = [];
                const map = new Map();
                map.set('(', ')')
                map.set('[', ']')
                map.set('{', '}')
                for (let i = 0; i < s.length; i++) { 
                    const c = s[i]
                    if (map.has(c)) { 
                        stack.push(c)
                    } else { 
                        const t = stack[stack.length - 1]
                        if (map.get(t) === c) { 
                            stack.pop()
                        } else { 
                            return false
                        }
                    }
                }
                // 栈空则表示匹配，栈不空则表示不匹配
                return stack.length === 0
            }

发表评论取消回复

表情：

评论列表（有 0 条评论，124人围观）

还没有评论，来说两句吧...

相关阅读

相关 C语言数据结构--栈括号匹配算法

今天这一期使用栈来完成括号匹配算法 ① 栈结构 typedef struct { char elem[Stack_Size];

雨点打透心脏的1/2处/ 2024年03月22日 10:44/ 0 赞/ 49 阅读

相关 java判断是否有效的括号

public static void main(String[] args) { System.out.println(isValid("()"

迷南。/ 2023年06月17日 12:52/ 0 赞/ 2 阅读

相关 [数据结构与算法]有效的括号（判断括号是否匹配），栈，字典

var isValid = function (s) { if (s.length % 2 === 1) {

Bertha 。/ 2022年12月06日 04:17/ 0 赞/ 125 阅读

相关数据结构栈的应用括号匹配

include <stdio.h> int main() { int n, top, j; char str[1

爱被打了一巴掌/ 2022年09月19日 01:30/ 0 赞/ 181 阅读

相关【算法】判断括号是否匹配

描述现在，有一行括号序列，请你检查这行括号是否配对。输入第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是

柔光的暖阳◎/ 2022年08月26日 08:43/ 0 赞/ 167 阅读

相关数据结构——栈实现括号匹配

数据结构——栈实现括号匹配 > 真正学习之后，才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做，原来这么简单。![敲打][knock.gif] >

红太狼/ 2022年06月17日 08:43/ 0 赞/ 198 阅读

相关利用栈判断括号是否匹配

update on 20210826 主要思想使用栈进行匹配，但是不要把所有的字符都入栈，只需要将三种括号入栈即可，这样会简化控制逻辑。代码如下： i

素颜马尾好姑娘i/ 2022年06月17日 05:14/ 0 赞/ 199 阅读

相关判断括号是否匹配

/\judege whether every bracket appears in pairs\/ \include<stdio.h> \include<string.

小灰灰/ 2022年06月13日 00:43/ 0 赞/ 173 阅读

相关数据结构与算法判断括号是否匹配

数据结构与算法判断括号是否匹配一、简单说明判断表达式中的半弧括号是否匹配，例如:"(56-20)/(4+2)"、"(1+(56-20)/(4+2))-(2\3

心已赠人/ 2022年05月26日 03:38/ 0 赞/ 163 阅读

相关数据结构【栈】（九）：使用栈检查括号是否匹配

问题描述给一个字符串表达式，包含一个或多个括号，现要求使用栈检查该字符串表达式中的括号是否平衡。解答思路遍历字符串中的每个字符，如果： 1）出现左括号则进

╰+攻爆jí腚メ/ 2022年02月28日 03:30/ 0 赞/ 198 阅读