This is one of the easier coding tasks, but you still can meet it in some preliminary tech screening. The problem looks like this:
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.Description taken from Leetcode (c).
How do you solve it?
We have been using this task for the tech screening. What is interesting is that how many people don’t really know how to deal with this (and mind you, this is an “Easy” category on Leetcode). Some people try to use regular expressions; some try to think up a brute-force solution going through the string and counting the opening and closing brackets. If you think about it, though, you will understand, that neither will suffice. For example, how can counting help with the easiest case of ([)]?
The solution that should jump to your mind, but may not if you never trained to solve coding problems, is a stack. Why the stack? Well, because the pair of braces or brackets can only be checked for completeness when you see a closing bracket; but that means that the opening one should be kept somewhere waiting and be on top of some data structure to check. And the structure which allows LIFO access is a stack. Happens that we have a ready-made Stack class in Java.
So, how does the simple solution look like?
Basic idea is, you start walking through the string. If the symbol is one of opening ones, you push it into a stack. If it’s closing, you peek into a stack and see if it’s a match. If yes, you pop it from the stack. You return true if the stack is empty in the end.
import java.util.*;
public class Groups{
private static final List<Character> OPEN = Arrays.asList('(', '{', '[');
private static final List<Character> CLOSE = Arrays.asList(')', '}', ']');
public static boolean groupCheck(String s){
if (s == null || s.length() == 0) {
return true;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char current = s.charAt(i);
if (isOpen(current)) {
stack.push(current);
} else {
if (stack.isEmpty()) {
return false;
}
char prev = stack.peek();
if (isMatch(prev, current)) {
stack.pop();
}
}
}
return stack.isEmpty();
}
private static boolean isOpen(char c) {
return OPEN.contains(c);
}
private static boolean isClose(char c) {
return CLOSE.contains(c);
}
private static boolean isMatch(char prev, char next) {
return isOpen(prev) && (OPEN.indexOf(prev) == CLOSE.indexOf(next));
}
}Is there any other way to solve this? What if the stack doesn’t come up to your mind? As always, there’s more than one way to solve a problem. Let’s look at this example: ([]){}.
Let’s try to replace correctly matched pairs:
“([]){}”.replace(“[]”, “”) => “(){}”.replace(“()”, “”) => “{}”.replace(“{}”, “”) => “”
So, we can just loop through the string replacing “{}”, “()” and “[]” with an empty string. When the result becomes empty, it means that all pairs are matched. What if it doesn’t become empty; how do we break from the cycle? Well, we need to check if the length of the string has changed after a round of replacements. If it hasn’t, then we break.
public class Groups{
public static boolean groupCheck(String s) {
int len;
do {
len = s.length();
s = s.replace("()", "");
s = s.replace("{}", "");
s = s.replace("[]", "");
} while (len != s.length());
return s.length() == 0;
}
}This looks even better; simple and readable, but is it better in truth? I’d say that no, not really. Why? Well, because the String class is immutable, and therefore every time we do that s.replace() we are creating a new string object on the heap.
So, how best to do that? Could we rewrite the code using the StringBuilder class? Well, not directly, because it doesn’t have a replaceAll method. You’d have to write it yourself using an existing replace method. There’s a StrBuilder class in Apache Commons library which does have this method, but it’s not a standard Java class, you’d have to add a dependency.
So, even this simple task can give some food for thought. For the interview, however, any of the solutions will do. If the stack isn’t the first thought in your head, you can do without.
| Reference: | Interview questions: verify the braces from our JCG partner Maryna Cherniavska at the Software development and other animals blog. |
GREAT Tutorial Maryna,
I’m curious whether you need List. It seems to me as soon as you come across a ‘non-open’ character you have to peek/pop from the stack. Likewise the isClose() method might not be necessary.
Have I missed something in the explanation?
— Edit —
My first sentence is incomplete: I’m curious whether you need a List for the Close characters ..
You are correct, the isClose() method is unused. We don’t need it while we assume that the string will only contain those chars. Also, I could do without the lists and just hardcode the values into the isOpen() method. It would take less resources. I just thought that this way is more readable, as the constants are extracted to the head of the class. But it could be an array and not a list, and that would also take up less resources.