Leetcode Valid Parentheses

Leetcode Valid Parentheses

过年无聊刷了几道题,更新一下博客(好久没更新了,心虚)。

https://leetcode-cn.com/problems/valid-parentheses/

一、题目

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1

示例 2

示例 3

示例 4

示例 5

二、解决方案

我的初步思路:

  1. 这题又是一道找规律题,所有例子中一定有规律,找到就能解决。

接下来仔细观察例子:

  1. 示例1、示例2中,明显存在括号配对的情况,可以相互抵消。
  2. 示例3、示例4中,存在不配对的情况,不能相互抵消。

这里我想到了一个形象的例子,“消消乐”游戏。这题的“左括号”和“右括号”可以配对消除,如果输入的所有括号都能彼此对应,那么一一消除后,最后一个字符都不会剩下,那么我们就认为字符串有效,反之,如果最后剩下了字符,那么字符串当然是无效的。

现在我们要考虑的,就是如何一一对应这些“括号”,这就需要详细观察例子5。假设现在有一个栈,我们把“{[]}”逐一扔进这个栈中,就会有如下思路:

  1. 入栈“{”。
  2. 入栈“[”。
  3. 入栈“]”,和栈顶元素“[”对应,同时出栈。
  4. 入栈“}”,和栈顶元素“{”对应,同时出栈。
  5. 所有元素入栈完毕,检查栈。如果为空,返回true,否则返回false。

顺着这个思路就可以开始写。

最终代码为:

结果为:

三、总结

很久没做题,只能做做easy练手。

这题还是比较简单的,需要的只是细致的观察。

发布者

xie4ever

发表评论

电子邮件地址不会被公开。