leetcode Stack

leetcode 20题

Posted by franki on November 29, 2020

leetcode 20题 有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1

输入: "()"
输出: true

示例 2

输入: "()[]{}"
输出: true

示例 3

输入: "(]"
输出: false

题解：

思路

使用 stack 先入后出的原则，存放左括号，每次遇到右括号，就出栈，栈顶字符与当前字符的相对应的右括号比对，如果相等则说明正确，继续其他字符的比对，否则，不是有效的括号

代码

var isValid = function(s) {
    if (s.length % 2 !== 0) return false;
    // map
    const map = {
        '(': ')',
        '{': '}',
        '[': ']',
    };
    // stack
    const stack = [];
    for (let i =0; i<s.length; i++) {
        const curStr = s.charAt(i);
        if (curStr === "(" || curStr === "{" || curStr === "[") {
            stack.push(curStr);
        } else {
            popStr = stack.pop();
            if (curStr !== map[popStr]) {
                return false;
            }
        }
    }
    return stack.length === 0;
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS