Tuesday, December 9, 2014

Checking if one string is a rotation of another string. [Coding Question][Java]

Q. Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g., "waterbottle" is a rotation of "erbottlewat").

Algorithm:

1. String x = s1+s1; [ waterbottlewaterbottle ]
2. Now the other string should be a substring of this string, if that string is a rotation of the other string.

waterbottlewaterbottle

Source:

public class Code {
    public static boolean checkRotation(String s1, String s2){        
        if(s2.length()<s1.length()) return false;
         
        String s1s1 = s1+s1;
        return isSubstring(s1s1, s2);
    }
    
    public static boolean isSubstring(String original, String beingChecked){
        int sLength = original.length();
        int tLength = beingChecked.length();
        
        int j=0, i = 0;
        boolean found = false;
        
        for(; j < tLength && i <= sLength - tLength;++i){
            int i2 = i;
            while(original.charAt(i2) == beingChecked.charAt(j)){ 
                i2++;j++;
                if(i2==sLength || j==tLength){found = true; break;}
            }
            if(found)break; else j = 0;
        } 
        return found;
    }
    
    public static void main(String[] args){
        System.out.println(isSubstring("abcbcda", "bcd"));
        System.out.println(isSubstring("ttqttyf", "tty"));
        System.out.println(checkRotation("waterbottle", "erbottlewat"));
        System.out.println(checkRotation("aaabccddss", "saaabccddxs"));
    }
}

Output:
 
true
true
true
false

No comments:

Post a Comment