Identification of valid parentheses with different data structures

The problem is defined as follows: 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.

The idea is about using Stack to solve the problem, say if a parentheses has only the left part “(, {, [” without the right part “], }, )” to close it properly, then the left part will be pushed to the stack, until we find the corresponding right part and pop the left part out of the stack. At last, if the stack is empty the input String must contains the valid parentheses.

Firstly, we create a HashMap with 3 parentheses pairs.

private static final Map<Character, Character> pair = new HashMap<>(3);
static {
	pair.put('(', ')');
	pair.put('[', ']');
	pair.put('{', '}');
}

The first solution using the idea discussed above along with Stack and the predefined three parentheses pairs in map:

public boolean isValid(String s) {
	Stack<Character> stack = new Stack<>();
	for (int i = 0; i < s.length(); i++) {
		Character c = Character.valueOf(s.charAt(i));
		if (stack.isEmpty() || !c.equals(pair.get(stack.peek()))) {
			stack.push(c);
		} else {
			stack.pop();
		}
	}
	return stack.isEmpty();
}

After that, I tried LinkedList as the alternative data structure as well.

public boolean isValid(String s) {
	LinkedList<Character> stack = new LinkedList<>();
	for (char ca : s.toCharArray()) {
		Character c = Character.valueOf(ca);
		if (stack.isEmpty() || !c.equals(pair.get(stack.getLast()))) {
			stack.addLast(c);
		} else {
			stack.removeLast();
		}
	}
	return stack.isEmpty();
}

Apparently with no surprise, the speed is nearly the same. Also the toCharArray() brings almost nothing to the performance, it looks however neater 🙂

Please Note that the ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

public boolean isValid(String s) {
	Deque<Character> stack = new ArrayDeque<>();
	for (char ca : s.toCharArray()) {
		Character c = Character.valueOf(ca);
		if (stack.isEmpty() || !c.equals(pair.get(stack.peek()))) {
			stack.push(c);
		} else {
			stack.pop();
		}
	}
	return stack.isEmpty();
}