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. ((((((((((.