LeetCode 5. Valid Parentheses [Strings, Stack]

Problem:

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

 

-Summary-

1. Stack the bracket only if the current index of the character is an open bracket

2. Otherwise, we pop from the stack and compare it with the current closed bracket. (If match, keep continue, otherwise return False)

3. After the loop, if the length of the stack is not 0, which means we have unfinished brackets. return False. 

4. If the length of the stack is 0, return True.

Time Complexity: O(n)

--> We need to compare all characters in the string.

Space Complexity: O(n)

--> In a worst-case, we need to use the stack for all characters in the string.

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]