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;
}
}
没有评论:
发表评论