2014年5月10日星期六

Recursive Solution - Scramble String

This problem can be resolved by recursive call, and need to verify if both have same letters set to reduce duplicates. Assume AB and CD, the recursive call will verify A==C && B==D || A == D && B == C, that make the size equal too.

There are some assumptions, like ASCII.

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length() != s2.length()){
            return false;
        }
       
        if(!hasSameLetters(s1, s2)){
            return false;
        }
       
        if(s1.equals(s2)){
            return true;
        }
        if(s1.length() == 2 && (s1.charAt(0) == s2.charAt(1) && s1.charAt(1) == s2.charAt(0))){
            return true;
        }
     
        for(int mid  = 1; mid < s1.length(); mid++){ //Start from ONE, Otherwise, keep looping (0, 0), (0, length) !!!
            String s11 = s1.substring(0, mid);
            String s12 = s1.substring(mid, s1.length());
            String s21 = s2.substring(0, mid);
            String s22 = s2.substring(mid, s2.length());
            if(hasSameLetters(s11, s21) && hasSameLetters(s12, s22) && isScramble(s11, s21) && isScramble(s12, s22))
                return true;
           
            s21 = s2.substring(s2.length() - mid, s2.length());
            s22 = s2.substring(0, s2.length() - mid);
            if(hasSameLetters(s11, s21) && hasSameLetters(s12, s22) && isScramble(s11, s21) && isScramble(s12, s22))
                return true;
        }
        return false;
    }
    //Function to avoid reductant recursive calls... This is also a question to ask during the interview... I assumeed two Strings alwasy have the same char sets... need to verify with interviewer
    private boolean hasSameLetters(String s1, String s2){
        if(s1 == null && s2 ==null){
           return true;
        }
        if(s1.length() != s2.length()){
            return false;
        }
        //assume ascII
        int[] process = new int[256];
        for(int i = 0; i < s1.length(); i++){
            process[s1.charAt(i) - 48]++;
            process[s2.charAt(i) - 48]--;
        }
        for(int j = 0; j < 256; j++){
            if(process[j] != 0){
                return false;
            }
        }
        return true;
    }
}

没有评论: