Last active
June 10, 2019 19:42
-
-
Save netstart/a53ebf99c01cf7aaeab79fa54bea11e8 to your computer and use it in GitHub Desktop.
Braces balanced solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
You are designing a compiler for a C++ program and need to check that braces in any given file are balanced. | |
Braces in a string are considered to be balanced if the following criteria are met: | |
All braces must be closed. Braces come in pairs of the form (), {} and []. The left brace opens the pair, and the right one closes it. | |
In any set of nested braces, the braces between any pair must be closed. | |
For example, [{}] is a valid grouping of braces but [{]} is not. | |
Function Description | |
Complete the function braces in the editor below. The function must return an array of strings where the string at each index i denotes whether or not the braces were balanced in values[i]. The array should consist of strings YES or NO aligned with their indices in values. | |
braces has the following parameter(s): | |
values[values[0],...values[n-1]]: an array of strings to analyze | |
Constraints | |
1 ≤ n ≤ 15 | |
1 ≤ | values[i] | ≤ 100 | |
Each values[i] consists of (, ), {, }, [, and ] only. | |
Input Format For Custom Testing | |
Input from stdin will be processed as follows and passed to the function: | |
The first line contains an integer n, the number of elements in values. | |
Each of the next n lines contains a string that describes values[i] where 0 ≤ i < n. | |
Sample Case 0 | |
Sample Input For Custom Testing | |
2 | |
{}[]() | |
{[}]} | |
Sample Output | |
YES | |
NO | |
Explanation | |
values[0]: {}[]() meets the criteria for a balanced string, so index 0 in the return array should contain the string YES. | |
values[1]: {[}]} contains unmatched braces between a matched pair in the substrings [}, {[}, and [}], so index 1 in the return array should contain the string NO. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.IOException; | |
public class Solution { | |
static String[] braces(String[] values) { | |
String[] answer = new String[values.length]; | |
for (int i = 0; i < values.length; i++) { | |
String currentString = values[i]; | |
answer[i] = "NO"; | |
if (currentString.length() % 2 != 0) { | |
answer[i] = "NO"; | |
break; | |
} | |
if (isPolindromeBraces(currentString)) { | |
answer[i] = "YES"; | |
break; | |
} | |
if (openCloseAtSequence(currentString)) { | |
answer[i] = "YES"; | |
break; | |
} | |
} | |
return answer; | |
} | |
static boolean openCloseAtSequence(String currentString) { | |
int half = currentString.length() / 2; | |
for (int i = 0; i < half; i = i + 2) { | |
if (isCorrespondents(i, i + 1, currentString)) { | |
return true; | |
} | |
} | |
return false; | |
} | |
static boolean isPolindromeBraces(String currentString) { | |
int half = currentString.length() / 2; | |
for (int start = 0; start < half; start++) { | |
for (int end = currentString.length() - 1; end > half; end--) { | |
if (isCorrespondents(start, end, currentString)) { | |
return true; | |
} | |
start++; | |
} | |
} | |
return false; | |
} | |
static boolean isCorrespondents(int start, int end, String s) { | |
return openClose(s.charAt(start), s.charAt(end), '(', ')') || | |
openClose(s.charAt(start), s.charAt(end), '[', ']') || | |
openClose(s.charAt(start), s.charAt(end), '{', '}'); | |
} | |
static boolean openClose(char charA, char charB, char charOpen, char charClose) { | |
return charA == charOpen && charB == charClose; | |
} | |
public static void main(String[] args) throws IOException { | |
System.out.println(Solution.braces(new String[]{"{[()]}"})[0]);// YES | |
System.out.println(Solution.braces(new String[]{"{}[]()"})[0]);// YES | |
System.out.println(Solution.braces(new String[]{"{[}]}"})[0]);// NO | |
System.out.println(Solution.braces(new String[]{"))))))"})[0]);// NO | |
System.out.println(Solution.braces(new String[]{")))))((((("})[0]);// NO | |
System.out.println(Solution.braces(new String[]{"((((((("})[0]);// NO | |
System.out.println(Solution.braces(new String[]{"{{[]"})[0]);// NO | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment