1
\$\begingroup\$

A string of brackets is considered correctly matched if every opening bracket in the string can be paired up with a later closing bracket, and vice versa. For instance, “(())()” is correctly matched, whereas “)(“ and “((” aren’t. For instance, “((” could become correctly matched by adding two closing brackets at the end, so you’d return 2.

Given a string that consists of brackets, write a function bracketMatch that takes a bracket string as an input and returns the minimum number of brackets you’d need to add to the input in order to make it correctly matched.

My approach:

 import java.io.*;
 import java.util.*;

 class Solution {

  static int bracketMatch(String text) {
    // your code goes here
    //Maintain 2 variables
    int ob = 0;//ob
    int cb = 0;//cb
    int wb= 0;//wb

    for( int i = 0; i < text.length(); i++ )
      {
          //Check for openBracket
          if( text.charAt(i) == '(')
             ob++;

          //Check for closeBracket
          if( text.charAt(i) == ')')
             cb++;

          //Check if closeBracketct > openBracketct
          if( cb > ob )
          { 
            wb++;
            ob = 0;
            cb = 0;
          }
      }
    return (wb + (ob - cb));
  }

  public static void main(String[] args) {
    //System.out.println(bracketMatch("())("));
    //System.out.println(bracketMatch("(((())))"));
    System.out.println(bracketMatch("(((())"));
  //  System.out.println(bracketMatch("))))"));
  }

}

I have a few questions regarding the above code:

1) How can I further optimize this code?

2) Am I using too many variables?

3) Is there a better approach than mine?

Reference

\$\endgroup\$
  • 3
    \$\begingroup\$ You need to use a stack. This question is from cracking the coding interview \$\endgroup\$ – Gilad Feb 4 '18 at 5:33
  • \$\begingroup\$ Thanks. Any other solution where I can reduce the number of variables required? \$\endgroup\$ – Anirudh Thatipelli Feb 4 '18 at 5:41
  • 1
    \$\begingroup\$ You may find the filter part of this answer useful, basicly you keep a stack, and make sure that when you see a closing bracket you have already seen an opening bracket to match it \$\endgroup\$ – jrtapsell Feb 4 '18 at 22:15
2
\$\begingroup\$

We dont need close variable if we can decrease open by 1 when close bracket is found.

public class MatchBrackets{

    public static int matchBrackets(String brackets){

      int open = 0;
      int count =0;

     for(int i=0;i<brackets.length();i++){
        if(brackets.charAt(i)=='('){
        open++;
        }else if(brackets.charAt(i)==')'){
         open--;
        }
        if(open<0){
        count++;
        open++;
     }
  }
  return count+open;
}

  public static void main(String[] args) {

  System.out.println(matchBrackets("())("));
  System.out.println(matchBrackets("(((())))"));
  System.out.println(matchBrackets("))))"));
}}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.