Answer» - You will be GIVEN string str containing characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, your task is to determine whether the brackets are balanced or not.
- These conditions should satisfy for balanced brackets:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Approach: - To keep track of two brackets to be compared keep two variables i and j.
- Maintain a count variable and increment its VALUE on encountering an opening bracket and DECREMENTS on encountering a closing bracket.
- Assign values of j and i as- j = i, i = i + 1 and counter++ when opening brackets are encountered.
- When Closing brackets are encountered do count– i,e decrement its value and compare brackets at i and j,
- If brackets at i and j match, then SUBSTITUTE ‘#’ in the string at ith and jth position. Increment i and decrement j until non ‘#’ value is encountered or j ≥ 0.
- If brackets at i and j do not match, return false.
- If count != 0, return false.
import java.util.*; class InterviewBit{ static String str = "[[]][]()"; static int Count = 0; static int i = 0; static int j = -1; static int helperFunc(char compare) { Count--; char temp = str.charAt(j); if (j > -1 && temp == compare) { str = str.replace(str.charAt(i),'#'); str = str.replace(str.charAt(j),'#'); temp = str.charAt(j); while (j >= 0 && temp == '#') j--; i++; return 1; } else return 0; } static boolean isValid() { if (str.length() == 0) return true; else { int result; while (i < str.length()) { char temp = str.charAt(i); if(temp=='}') { result = helperFunc('{'); if (result == 0) { return false; } } else if(temp == ')') { result = helperFunc('('); if (result == 0) { return false; } } else if(temp == ']') { result = helperFunc('['); if (result == 0) { return false; } } else { j = i; i++; Count++; } } if (count != 0) return false; return true; } } public static void main(String args[]) { if (isValid()) System.out.println("No"); else System.out.println("Yes"); }}
|
