Any Java Solution

interview-questions
Tags: #<Tag:0x00007f2424a837f8>

#1

Any solution using java?


#2
public int isScramble(final String a, final String b) {
    if (a.length() != b.length()) {
        return 0;
    }
    int n = a.length();
    if (n == 0) {
        return 1;
    }
    if (a.equals(b)) {
        return 1;
    }

    char[] a1 = a.toCharArray();
    char[] b1 = b.toCharArray();
    Arrays.sort(a1);
    Arrays.sort(b1);
    if (!new String(a1).equals(new String(b1))) {
        return 0;
    }


    for (int i = 1; i < n; i++) {
        if (isScramble(a.substring(0, i), b.substring(0, i)) == 1 &&
                isScramble(a.substring(i, n), b.substring(i, n)) == 1) {
            return 1;
        }
        if (isScramble(a.substring(0, n - i), b.substring(i, n)) == 1 &&
                isScramble(a.substring(n - i, n), b.substring(0, i)) == 1) {
            return 1;
        }
    }
    return 0;
}

#3

Found a really good explanation of this question


#4

public int isScramble(final String a, final String b) {
if(a.compareTo(b)==0)
return 1;
else if(a.length()<= 1)
return 0;

    String keyValue=a+" "+b;

    if ( map.containsKey(keyValue) ) {
        return map.get(keyValue);
    }

    int n=a.length();
    int flagScramble=0;
    for(int i = 1;i <= n-1;i++){
        
      
        boolean cond1=(isScramble(a.substring(0, i),b.substring(n - i,n))==1 && isScramble(a.substring(i, n),b.substring(0, n-i))==1);
      
        boolean cond2=(isScramble(a.substring(0, i),b.substring(0, i))==1  && isScramble(a.substring(i, n),b.substring(i, n))==1);

         if(cond1 || cond2){
            flagScramble = 1;
            break;
        }
    }
    map.put(keyValue, flagScramble);
    return flagScramble;
}

#5
   HashMap<String, Integer> hm;

public int isScramble(final String A, final String B) {
    hm = new HashMap<>();
    return isScrambled(A, B);
}

public int isScrambled(String A, String B) {
    if (hm.containsKey(A + "#" + B)) {
        return hm.get(A + "#" + B);
    }

    if (A.equals(B)) {
        hm.put(A + "#" + B, 1);
        return 1;
    }

    if(A.length()==1 && B.length()==1)return 0;
    int n = A.length();

    int straight_match = 0, rev_match = 0;

    for (int i = 1; i <n; i++) {
        if ((isScrambled(A.substring(0, i), B.substring(n - i)) == 1
                && isScrambled(A.substring(i), B.substring(0, n - i)) == 1)) {
            rev_match = 1;
            break;
        }



            if ((isScrambled(A.substring(0, i), B.substring(0, i)) == 1
                    && isScrambled(A.substring(i), B.substring(i)) == 1)) {
                straight_match = 1;
                break;
            }
    }

    if (rev_match == 1 || straight_match == 1) {
        hm.put(A + "#" + B, 1);
    }else{
        hm.put(A + "#" + B, 0);
    }
    return hm.getOrDefault(A + "#" + B, 0);
}