算法养成记：有效括号

• 2020 年 3 月 10 日
• 筆記

LeetCode20

Valid Parentheses 验证括号

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1.Open brackets must be closed by the same type of brackets.

2.Open brackets must be closed in the correct order.

中文意思就是：

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

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

Example 1:

Input: "()" Output: true

Example 2:

Input: "()[]{}" Output: true

Example 3:

Input: "(]" Output: false

Example 4:

Input: "([)]" Output: false

Example 5:

Input: "{[]}" Output: true

在实际测试里，

执行耗时是：2ms，1ms

内存消耗是:37.4MB,37.3MB

这题不难，但是尝试了好多种写法，一直都是2ms，接近崩溃。直到想到判断其他括号的时候，如果匹配上了就可以跳出循环了，用了图二的continue，出现1ms，击败98.92%的用户，悬着的心才下来，但是测试效果也不太稳定，希望各位小伙伴也提供下思路。

有个收获就是，之前写栈的时候，判断空，直接就用了stack.empty()；测试中，使用这个方法一直都比stack.size()>0好内存高，看了下empty()的方法，里面还是去拿了size()来判断，还套了两层，这的确是没有必要了。

数据结构和算法一直都是程序员面试重点。写好每一个方法，每一个接口，程序的效率也会越来越高。为了学习和巩固数据结构和算法，我们特别创作了《呆萌程序员–明明凯凯算法养成记》，每天更新一篇数据结构知识点或者刷一道LeetCode题目。算法都会在LeetCode上测试。当然答案不唯一，由于能力有限，实现方法不一定是最好的，也希望各位小伙伴一起来学习分享~