Given a string s
containing the characters [
]
(
)
{
}
, return whether the parentheses are valid.
A set of parentheses is "valid" if every opened parenthesis has a matching closed parenthesis of the same type, and is closed in the correct order.
We'll solve this problem by walking left to right. It's always valid to open a new opened parenthesis (
{
[
, as we walk.
The only time a string is invalid is if we come across a closing parenthesis )
}
]
in the wrong place.
To solve this problem, we need to make sure every closing parenthesis matches the most recent open parenthesis.
Here's an example of this. When we get to the 4th character, the most recent unmatched open parenthesis is (
. This means the only allowed closing parenthesis is )
.
To check if this holds, you want to be able to efficiently find the most recent open parenthesis. You can do this by storing all of the opened parentheses that you've seen so far in an Array called opened
.
You always append parentheses to the array, which means that the most recent opened parenthesis will always be at the end of the array.
This means you can always use the last entry of opened
to check if the current character is valid. Here's an example, when we get to the 5th character in the below string:
Whenever you match a closed parenthesis with an open parenthesis, you should pop that open parenthesis from opened
, because it's been matched.
Here's the full code to solve this problem:
This is technically a Stack problem, since we're only adding/removing elements from the end of the opened
array.
Time Complexity O(n). We do an O(1) operation n times.
Normally adding/removing elements in an array is O(n). But since we're adding and removing elements from the very end of the array, all operations are O(1).
Space Complexity O(n). opened
might grow to size n if the string is all open parentheses.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()