ruslanbes2
BAN USERSolution with Strings so that you don't care if the numbers are too big for long:
package com.careercup.ruslanbes.jumbled;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static String[] jumbledNumbers(final int n) {
return listToArray(jumbledNumbersInternal(n, false));
}
protected static List<String> jumbledNumbersInternal(final int n, boolean leadingZeroes) {
final String[] digits = {"0", "1", "2", "3", "4", "5", "6" ,"7", "8","9"};
if (n == 1) {
return Arrays.asList(digits);
}
final List<String> oldNumbers = jumbledNumbersInternal(n-1, true);
final List<String> numbers = new LinkedList<>();
final byte zero = (byte)'0';
final byte one = zero+1;
final byte nine = zero+9;
for (String s: oldNumbers) {
final byte c = (byte)s.charAt(0);
if (c != zero || leadingZeroes) {
numbers.add(String.valueOf((char)(c)) + s);
}
if (c > one || leadingZeroes && c > zero) {
numbers.add(String.valueOf((char)(c-1)) + s);
}
if (c < nine) {
numbers.add(String.valueOf((char)(c+1)) + s);
}
}
return numbers;
}
protected static String[] listToArray(List<String> list) {
String[] array = new String[list.size()];
for(int i = 0; i < array.length; i++) {
array[i] = list.get(i);
}
return array;
}
}
Not sure what is the best and worst case here. Also just printing a list of numbers is more than O(n) and should be around 9*3^(n-1) so it's O(3^n).
And calculating the number of jumbled numbers should be O(1) although I'm too lazy to figure out the exact formula
Easy solution with complexity O(mnlogm). Can be improved if instead of using sort you use a more complex approach - use hashing or a Map of letters.
package com.careercup.ruslanbes.q5683479172874240;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
public class Main {
public static int[] findAnagrams(String needle, String stack) {
List<Integer> anagrams = new LinkedList<>();
char[] needleDict = getDict(needle);
int m = needle.length();
int n = stack.length();
for(int i = 0; i < n-m+1; i++){
char[] stackDict = getDict(stack.substring(i, i+m));
if (Arrays.equals(needleDict, stackDict)) {
anagrams.add(i);
}
}
return listToArray(anagrams);
}
protected static char[] getDict(String s) {
char[] sDict = s.toCharArray();
Arrays.sort(sDict);
return sDict;
}
protected static int[] listToArray(List<Integer> list) {
int[] array = new int[list.size()];
for(int i = 0; i < array.length; i++) {
array[i] = list.get(i);
}
return array;
}
}
First of all, my Test Set. Use it to check your solution (hint: many of the solutions here fail it)
class MainTest {
@Test
void isBalanced() {
assertTrue(Main.isBalanced(""));
assertTrue(Main.isBalanced("()"));
assertTrue(Main.isBalanced("(*)"));
assertTrue(Main.isBalanced("(*)(*)"));
assertTrue(Main.isBalanced("*"));
assertTrue(Main.isBalanced("**"));
assertTrue(Main.isBalanced("*)"));
assertTrue(Main.isBalanced("*(((()())()))())"));
assertFalse(Main.isBalanced("*()("));
assertFalse(Main.isBalanced("**()("));
assertFalse(Main.isBalanced("**(**)*("));
assertFalse(Main.isBalanced(")**"));
assertTrue(Main.isBalanced("****()))))"));
assertTrue(Main.isBalanced("****())))"));
assertFalse(Main.isBalanced("****())))))"));
assertFalse(Main.isBalanced("***********************(((((()"));
assertFalse(Main.isBalanced("(((()())()))())"));
assertTrue(Main.isBalanced("*(((()())())*())"));
}
@Test
void isBalanced5() {
assertTrue(Main.isBalanced("(*)(*)(**"));
}
@Test
void isBalanced10() {
assertTrue(Main.isBalanced("*(((()())())())"));
}
}
My approach solves it in O(n^2). And handles all of the cases regardless of the number and position of characters in a string. It's pretty brute-force but it does the job. This is a solution for the simple case. For the case with "[]" and "{}" you just have to call it 3 times passing bracket chars as parameters
public class Main {
public static boolean isBalanced(String exp){
// Empty string is balanced by definition
if (exp.length() == 0) {
return true;
}
// edge cases - no point in looking further
if (exp.charAt(0) == ')' || exp.charAt(exp.length()-1) == '(') {
return false;
}
// find all (), (*), (**), ... cases and clear the brackets
for (int i = 0; i < exp.length(); i++) {
if (exp.charAt(i) == ')') {
for (int j = i - 1; j >= 0; j--) {
if (exp.charAt(j) == ')') {
break;
} else if (exp.charAt(j) == '(') {
exp = replaceString(exp, i, j);
break;
}
}
}
}
// find all *), *_), *___), ... cases and use the stars as left brackets
for (int i = 0; i < exp.length(); i++) {
if (exp.charAt(i) == ')') {
for (int j = i - 1; j >= 0; j--) {
if (exp.charAt(j) == '*') {
exp = replaceString(exp, i, j);
break;
}
if (j == 0) {
return false;
}
}
}
}
// same for (*, (_*, (___*
for (int j = exp.length() - 1; j >= 0; j--) {
if (exp.charAt(j) == '(') {
for (int i = j + 1; i < exp.length(); i++) {
if (exp.charAt(i) == '*') {
exp = replaceString(exp, i, j);
break;
}
if (j == exp.length() - 1) {
return false;
}
}
}
}
// if there any brackets left, then we ran out of stars
return !exp.contains("(") && !exp.contains(")");
}
public static String replaceString(String exp, int i, int j) {
return exp.substring(0, j) + "_" + exp.substring(j + 1, i) + "_" +
(i == exp.length() - 1 ? "" : exp.substring(i + 1));
}
}
An improved version of Kapil's answer. In their code, it is missed the case when n1 is subnode of n2
Test Set:
- ruslanbes2 October 18, 2017