问题描述:
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are all valid but "(]"
and "([)]"
are not.
原问题链接:https://leetcode.com/problems/valid-parentheses/
问题分析
这个问题相对来说比较简单,我们要判断给定的字符串是否符合合法的符号对。可以用一个栈来辅助处理。当我们遍历数组的时候,碰到左边括号的时候就压栈。如果碰到右边括号的时候就先看是否和栈顶的元素形成一个合法的括号。如果是,则弹出栈顶的元素,否则就返回非法的结果。在最终这个流程处理结束之后再看栈是否为空,如果栈为空表示达到一个合法的结果,否则就是非法的。
针对具体的实现细节,里面也有一些小的可以优化的地方。比如说当我们判断当前输入的字符不是左括号的时候,作为合法的输入,栈应该是非空的。我们可以在这里判断一下,如果栈是空的就可以直接返回了。这样可以跳过一些情况。详细的实现如下:
public class Solution { public boolean isValid(String s) { if(s == null || s.length() < 1) return true; Stack<Character> stack = new Stack<>(); for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(c == '(' || c == '[' || c == '{') stack.push(c); else { if(stack.isEmpty()) return false; if(c == ')') { if(stack.peek() == '(') stack.pop(); else return false; } else if(c == ']') { if(stack.peek() == '[') stack.pop(); else return false; } else if(c == '}') { if(stack.peek() == '{') stack.pop(); else return false; } else return false; } } return stack.isEmpty(); } }
相关推荐
java lru leetcode :ice_cream: LeetCode ...Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
Parentheses 用栈判断括号匹配 Regular Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to ...
Parentheses 有效的括号 Stack / 栈 用栈实现配对 Daily Challenge 2020/08/14 28 Implement strStr() 实现 strStr() String / 字符串 循环遍历即可 algorithm-pattern: quick start 43 Multiply S
leetcode题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写并配有输入输出样例 代码清单如下: 序号 题目 程序源码 ...Parentheses.cpp 22 括号生成 G
Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
LeetCode字符串换行 Solve_Leetcode 复习的过程,来刷刷题,坚持坚持坚持! 逆波兰表达式 题目如下: 使用了 class Stack A more complete and consistent ...Valid Parentheses 题目如下: Stack泛型
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
leetcode 跳跃 LeetCode 力扣刷题70道! 数组 Array 力扣 485 最大连续1的个数 | Max Consecutive ...Parentheses 力扣 496 下一个更大的元素 | Next Greater Element I 力扣 232 用栈实现队列 | Implement
有效的括号](./Stack/valid-parentheses.md) Array 数组 [0004 寻找两个有序数组的中位数](./Array/README.md) [0045 跳跃游戏 II](./Array/jump-game-ii.md) [0053 最大子序和](./Array/maximum-subarray.md) [0041...
valid-parentheses 155 min-stack design-circular-deque trapping-rain-water 滑动窗口 通过窗口的大小不断调整来找到合适的值,或者窗口大小不变,通过左右移动来找到相应的结果 \ \ 其他 非 LeetCode 题,单纯在...
leetcode 2 有效括号 给定一个只包含字符'(' , ')' , '{' , '}' , '['和']'的字符串,确定输入字符串是否有效。 输入字符串在以下情况下有效: * 左括号必须由相同类型的括号封闭。 * 左括号必须以正确的顺序关闭。 ...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
第四章 Leetcode 题解 ...20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
20-有效的括号:valid-parentheses 150-逆波兰表达式求值:evaluate-reverse-polish-notation 155-最小栈:min-stack Tree 普通二叉树 94-二叉树中序遍历:inorder-traversal 100-相同的二叉树:same-tree 101-对称二叉树...
leetcode怎么改密码 Code leetcode easy 测试一下本地的... emmmmm之前修改了一下,现在用ssh提交 应该不用输入密码了吧 ~~emmmmm 先在这里立个flag!!...Valid Parentheses :cross_mark:暴力解法(未通过)
Parentheses] [21. Merge Two Sorted Lists] [53. Maximum Subarray] [70. Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II...
加油站 leetcode leetcode_java prepare for jobhunting. java version of Leetcode. easy 55 about takes 5 days medium 112 about takes 20 days hard ...Leetcode ...1.Valid Parentheses 2.Maximum
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
ValidParentheses HashMap 还有 Stack 栈 最佳实践,Deque = Stack public static boolean isValid(String s) { if(s.length() == 0 || s == null || s.length() %2 != 0) return false; Deque deque = new ...
Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock...