A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
20 Valid Parentheses
71 Simplify Path
84 Largest Rectangle in Histogram
85 Maximal Rectangle
150 Evaluate Reverse Polish Notation
155 Min Stack
173 Binary Search Tree Iterator
224 Basic Calculator
225 Implement Stack using Queues
232 Implement Queue using Stacks
255 Verify Preorder Sequence in Binary Search Tree
316 Remove Duplicate Letters
331 Verify Preorder Serialization of a Binary Tree
341 Flatten Nested List Iterator
385 Mini Parser
394 Decode String
402 Remove K Digits
439 Ternary Expression Parser
456 132 Pattern
496 Next Greater Element I
503 Next Greater Element II
581 Shortest Unsorted Continuous Subarray
591 Tag Validator
636 Exclusive Time of Functions
654 Maximum Binary Tree
682 Baseball Game
726 Number of Atoms
735 Asteroid Collision
739 Daily Temperatures
770 Basic Calculator IV
772 Basic Calculator III
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By
GitBook
20 Valid Parentheses
20.
Valid Parentheses
1. Question
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.
2. Implementation
思路:查看括号匹配问题,就看相应的符号是否对称,可以直接用stack做
1
class
Solution
{
2
public
boolean
isValid
(
String
s
)
{
3
Stack
<
Character
>
stack
=
new
Stack
<>
();
4
5
for
(
char
c
:
s
.
toCharArray
())
{
6
if
(
c
==
'('
)
{
7
stack
.
push
(
')'
);
8
}
9
else
if
(
c
==
'['
)
{
10
stack
.
push
(
']'
);
11
}
12
else
if
(
c
==
'{'
)
{
13
stack
.
push
(
'}'
);
14
}
15
else
if
(
stack
.
isEmpty
()
||
(
stack
.
pop
()
!=
c
))
{
16
return
false
;
17
}
18
}
19
return
stack
.
isEmpty
();
20
}
21
}
Copied!
3. Time & Space Complexity
时间和空间都是O(n)
Previous
Stack
Next
71 Simplify Path
Last modified
2yr ago
Copy link
Contents
20. Valid Parentheses
1. Question
2. Implementation
3. Time & Space Complexity