Check Rotation Using one isSubstring Call

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 suing only one call to isSubstring (e.g, "waterbottle" is a rotation of "erbottlewat"). All Strings are assumed lowercase.

Naive Thinking:限制条件是只能用一次 isSubstring()。假设没有这个条件，先考虑这道题怎么做。假设单词A 和单词B，单词A从某个字母开始将和单词B完全匹配，知道单词A结尾，剩下的部分正好可以用 isSubstring来判断是否 单词B的后面的部分，这里同时还引出了一个漏洞就是必须确保单词A和单词B具有同样的词频。

算法复杂度是O(n^2)

public boolean isRotation(String s1, String s2){
        // check same character set
        int freq[] = new int[26];
        for(int i = 0;i < s1.length();i++)
            freq[(int)(s1.charAt(i)-'a')]++;
        for(int i = 0;i < s2.length();i++)
            freq[(int)(s2.charAt(i)-'a')]--;
        for(int i = 0;i < freq.length;i++)
            if(freq[i]!=0) return false;
        // check rotation
        for(int i = 0;i < s1.length();i++)
            if(s1.charAt(i)==s2.charAt(0))
                if(isEnd(s1, i, s2)) return isSubstring(s1.substring(0,i),s2);
        return false;
    }

    private boolean isEnd(String s1, int index, String s2){
        for(int i = index,j = 0;i < s1.length();i++,j++)
            if(s1.charAt(i)!=s2.charAt(j)) return false;
        return true;
    }

    public boolean isSubstring(String s1, String s2){
        return s2.indexOf(s1) >= 0;
    }

Improved Way: 这道题是Cracking the Coding Interview 里String/Array那一章的最后一道题。它的做法我想都没想过，特别巧妙。

这里直接照搬它的解释：
s1 = waterbottle; Let x = wat, y = erbottle
s1 = xy;
s2 = erbottlewat;
s2 = yx;

s1s1 = xyxy;
s2 = yx;
s2 will always be a substring of s1s1.

算法复杂度是O(n)。

public boolean isRotation(String s1, String s2){
        if(s1.length() == s2.length() && s1.length() > 0){
            String s1s1 = s1 + s1;
            return isSubstring(s2, s1s1);
        }
        return false;
    }