CODEWITHSUNDEEP
javastringalgorithmstack
Twitter khuong291
Twitter khuong291

Reputation: 11692

How to check if a String contains close group brackets in Java

How to checks a string for correct grouping. For instance, the following groups are done correctly:

({})
[[]()]
[{()}]

The next are done incorrectly:

{(})
([]
[])

A correct string cannot close groups in the wrong order, open a group but fail to close it, or close a group before it is opened.

The input string that may contain any of the symbols "()" "{}" or "[]" to create groups. The output return True if the string is empty or otherwise grouped correctly, or False if it is grouped incorrectly.

May anyone give me some hint with this.

Upvotes: 2

Views: 3861

Answers (2)

Ling Zhong
Ling Zhong

Reputation: 1804

The main idea is to use a Stack to keep track of the next corresponding bracket expected. The following code will work:

public boolean isValid(String s) {
    HashMap<Character, Character> closeBracketMap = new HashMap<Character, Character>();
    closeBracketMap.put(')', '(');
    closeBracketMap.put(']', '[');
    closeBracketMap.put('}', '{');
    HashSet<Character> openBracketSet = new HashSet<Character>(
        closeBracketMap.values());
    Stack<Character> stack = new Stack<Character>();

    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        char cur = chars[i];
        if (openBracketSet.contains(cur)) {
            stack.push(cur);
        } else { // close brackets
            if (stack.isEmpty()) {
                return false;
            }
            if (closeBracketMap.get(cur) != stack.peek()) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.isEmpty();
}

Upvotes: 8

Twitter khuong291
Twitter khuong291

Reputation: 11692

I really don't want to use stack, after trying something around. Here is my solution. I think this is very clear and simple:

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;
  }
}

That means we will remove one by one bracket.

For example: String s = "[]({[]()})" (len = 10; s.length() = 10) it will remove "[]", "[]", "()". Then s = "({})" (s.length() = 4) it will continue to remove "{}". Then s = "()" (s.length() = 2), it will continue to remove "()". Then s = "" (s.length() = 0). It will break the loop because ( (len == 10) != (s.length() == 0) ). Then we will be able to check it is true. :)

Upvotes: 0

Related Questions