patternjavaMinor

Checking brackets nesting in a string

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

checkingstringnestingbrackets

Problem

I took a training challenge on Codility that checks for the proper nesting of brackets in a string. The brackets to be checked are {,},(,),[,]. I have written the following Java program which passes in O(n) time and space, but I have a feeling that the extra space I use can be reduced. Also I think that there must be a data structure that can handle this scenario more efficiently. Using an ArrayList instead of an array might help. What I need here is a critique of my code.

import java.util.HashMap;
class Solution {
    public int solution(String S) {
        char[] stack = new char[S.length()];
        int last = -1;
        HashMap hm = new HashMap();
        hm.put('}', '{');
        hm.put(')', '(');
        hm.put(']', '[');
        for(int i=0; i<S.length(); i++){
            char next = S.charAt(i);
            if(next == '}' || next == '{' || next == ')' || next == '(' ||
            next == ']' || next == '[')
            {
                if(last!=-1 && hm.containsKey(next) && stack[last] == hm.get(next)){
                    last--;
                }
                else{
                    last++;
                    stack[last] = S.charAt(i);
                }
            }
        }
        if(last == -1){
            return 1;
        }
        return 0;
    }
}

Solution

Naming

Class name: Solution A solution for what?

Method name: solution - again I ask: Solution for what?

Parameter name: S - And what on earth is S? Parameter names are by convention named beginning with a lowercase letter.

None of these three names are descriptive names. It is easier to read and understand code when the names tell a bit about what it is that the code does. Now, naming things are hard, and something that programmers do a lot. For this case, consider names such as BracketNestingVerifier, verify and input. You might even be able to come up with better names.

General things

-
Use Generics for your HashMap. Since Java 1.5, it's been possible to define which kind of HashMap it is. Is it a HashMap of `? ? No, in your case; it's HashMap



- 
Why do the method return an

int when it would make much more sense to return a true/false boolean

? Returning a boolean allows you to simplify the end of your method

if (last == -1) { // note the fixed spacing ;)
    return 1;
}
return 0;


To simply

return (last == -1);



Spacing

I find that code like this:

for(int i=0; i<S.length(); i++){


Is much more readable if you use spacing (and a better variable name for

 of course)

for (int i = 0; i < input.length(); i++) {


Algorithm

Now, about that algorithm... You have a variable called

stack

 and yet it isn't a stack structure, it's only an array. Using a somewhat real stack structure can be helpful. In the code below, I have used the

LinkedList class to provide this structure (Even though there is also a Stack class, I like the Deque interface and wanted to go with LinkedList

).

In this code, I have improved the variable names, the return type, and I am using a

HashSet to store all "special" characters in. The contains

 method of a HashSet is performing in constant speed, so you should not experience any significant lack of performance. I noticed that in your if-statement, you had hard-coded the values that were put into your

HashMap, this is what made me want to add the HashSet`.

To make this work, I had to flip the key/values of your HashMap. The key is now the starting character, and the target is the expected ending character.

The loop through the string here is pretty simple and straight-forward:

Have we waited for this character? If so, remove it from the list of expected characters we are waiting for (The "stack")

If the above is not true, does this character have a matching ending character? If it does, add it to the stack

Again, if the above also is not true, is this character regarded as a special character? If it is, then we know here already that we have failed so we can return from the method.

public boolean simonsVerify(String input) {
    HashMap matches = new HashMap();
    matches.put('{', '}');
    matches.put('(', ')');
    matches.put('[', ']');

    Set specialChars = new HashSet();
    Deque expected = new LinkedList();
    for (Entry ee : matches.entrySet()) {
        specialChars.add(ee.getKey());
        specialChars.add(ee.getValue());
    }

    for (int i = 0; i < input.length(); i++) {
        char next = input.charAt(i);
        Character expect = expected.peekLast();
        if (expect != null && expect == next) {
            expected.removeLast();
        }
        else if (matches.containsKey(next)) {
            expected.addLast(matches.get(next));
        }
        else if (specialChars.contains(next)) {
            return false;
        }
    }
    return true;
}

Here is the testing (with JUnit) I used, for both your original code and also for my method:

@Test
public void testVerifying() {
    assertTrue(verify("{,},({,}),[,]"));

    assertFalse(verify("{(,},({,}),[,]"));
    assertFalse(verify("{,)},({gfdgfd}),[,]"));
    assertFalse(verify("{(,}),({,}),[,]"));

    assertTrue(verify("{,},(,),[[,]]"));
    assertTrue(verify("{,},(,),[,]"));
    assertTrue(verify("{{,}},(,),[,]"));
    assertTrue(verify("{,},((,)),[,]"));
    assertTrue(verify("{,},(,),[,]"));
    assertTrue(verify("(), {{{,}}},(,),[,]"));
}

There might even be a better way to do this algorithm, this is just my way.

Code Snippets

if (last == -1) { // note the fixed spacing ;)
    return 1;
}
return 0;

for(int i=0; i<S.length(); i++){

for (int i = 0; i < input.length(); i++) {

public boolean simonsVerify(String input) {
    HashMap<Character, Character> matches = new HashMap<Character, Character>();
    matches.put('{', '}');
    matches.put('(', ')');
    matches.put('[', ']');

    Set<Character> specialChars = new HashSet<Character>();
    Deque<Character> expected = new LinkedList<Character>();
    for (Entry<Character, Character> ee : matches.entrySet()) {
        specialChars.add(ee.getKey());
        specialChars.add(ee.getValue());
    }

    for (int i = 0; i < input.length(); i++) {
        char next = input.charAt(i);
        Character expect = expected.peekLast();
        if (expect != null && expect == next) {
            expected.removeLast();
        }
        else if (matches.containsKey(next)) {
            expected.addLast(matches.get(next));
        }
        else if (specialChars.contains(next)) {
            return false;
        }
    }
    return true;
}

@Test
public void testVerifying() {
    assertTrue(verify("{,},({,}),[,]"));

    assertFalse(verify("{(,},({,}),[,]"));
    assertFalse(verify("{,)},({gfdgfd}),[,]"));
    assertFalse(verify("{(,}),({,}),[,]"));

    assertTrue(verify("{,},(,),[[,]]"));
    assertTrue(verify("{,},(,),[,]"));
    assertTrue(verify("{{,}},(,),[,]"));
    assertTrue(verify("{,},((,)),[,]"));
    assertTrue(verify("{,},(,),[,]"));
    assertTrue(verify("(), {{{,}}},(,),[,]"));
}

Context

StackExchange Code Review Q#41693, answer score: 6

Revisions (0)

No revisions yet.