2023-9-19

9-19

栈

题号20. 有效的括号

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

有效字符串需满足：

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

解题思路 首先我们可以总结一下什么时候是有效的，在栈顶的左括号必须和相对于的右括号对应才能闭合所以使用辅助栈来实现

function isValid(s: string): boolean {
    let stack1 = []// 用数组模拟栈
     // 定义左括号和右括号的对应关系
    const map = {
        '(': ')',
        '{': '}',
        '[': ']',
    }
    for(let i = 0;i<s.length;i++){
        const char = s[i]
        if(map[char]){
            // 如果是左括号，将其推入栈
            stack1.push(char)
        }else{
            // 如果是右括号，检查是否与栈顶的左括号匹配
            const top = stack1.pop()
            if(char!==map[top]){
                return false // 不匹配则字符串无效
            }
        }
    }
    // 最后，栈应该为空，如果不为空，说明有未闭合的括号
    return stack1.length === 0
};