Reference: LeetCode
Difficulty: Easy

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: An empty string is also considered valid.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: "()"
Output: true

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

Analysis

Stack

For each character ch in input string, before pushing check it is matched with the top element in the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input String: "([])"

( stack is empty, push "("
-- bottom --

[ top is "(", push "["
(
-- bottom --

( top is "[", matched with the next pushing "]". Pop "["
-- bottom --

top is "(", matched with the next pushing ")". Pop "("
-- bottom --
Empty Stack ==> Valid!

Note:

My Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : s.toCharArray()) {
if (stack.size() == 0) { // empty, just push
stack.push(ch);
} else {
if (isMatched(stack.peek(), ch)) { // top: left, ch: right
stack.pop();
} else {
stack.push(ch);
}
}
}
return stack.size() == 0;
}

private boolean isMatched(char left, char right) {
if (left == '(') {
return right == ')';
}
if (left == '[') {
return right == ']';
}
if (left == '{') {
return right == '}';
}
return false;
}

Other Solution #1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
// Push any open parentheses
if (ch == '(' || ch == '[' || ch == '{')
stack.push(ch);
// Close parentheses
else if (ch == ')' && stack.size() > 0 && stack.peek() == '(')
stack.pop();
else if (ch == ']' && stack.size() > 0 && stack.peek() == '[')
stack.pop();
else if (ch == '}' && stack.size() > 0 && stack.peek() == '{')
stack.pop();
else
return false; // other characters
}
return stack.size() == 0;
}

Other Solution #2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.size() == 0;
}

Time: $O(N)$
Space: $O(N)$ e.g. ((((((((((.


Comment