Categories
LeetCode

LeetCode 20. Valid Parentheses[stack] Java

Source URL: https://leetcode.com/problems/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.

Note that an empty string is also considered valid.

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

This is a textbook usage of the stack. The stack is born to solve nest structures. Every time we meet a “(“, “[” or “{“, we push it to the top of the stack, and every time we meet a “)”, “]” or “}”, we pop the top of the stack. And we compare the current close bracket with the open bracket popped up. If they are matched, we know it is valid.

This is the code, my stack:

Push open bracket, meet close bracket pop, and compare them:

Running time 1ms, faster than 98.28% java submission。

Github:https://github.com/tinyfool/leetcode/tree/master/src/p0020

Other problems related to stack and queue, see also Stack and Queue Data Structure (Java code and Leetcode problems)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.