Checking whether one string is a rotation of another

Question

Given a method isSubstring, two strings s1 and s2, check whether s1 is a rotation of s2 using only one call to isSubstring.

Any comments on the code below?

I would like to check the complexities as well:

For isSubstring:

• runtime: \$O(n^2)\$
• memory: in place

For isRotation:

• runtime: \$O(n^2)\$
• memory: \$O(n)\$

import static org.junit.Assert.*;
import org.junit.Test;
public class Solution {
 // Find whether string s1 is a rotation of string s2
 // using only one call to isSubstring
 static boolean isSubstring(String s1, String s2) {
 // return true if s1 is a substring of s2
 // false otherwise
 int n1 = s1.length();
 int n2 = s2.length();
 for (int i = 0; i < n2; i++) {
 if (i+n1>n2){
 return false;
 }
 else if (s1.equals(s2.substring(i,i+n1))) {
 return true;
 }
 }
 return false;
 }
 static boolean isRotation(String s1, String s2) {
 // return true if s2 is a rotation of s1
 // false otherwise
 // concatenate all the rotated strings of s1
 StringBuffer allRotated = new StringBuffer();
 int n1 = s1.length();
 int n2 = s2.length();
 if (n1 != n2) {
 return false;
 }
 allRotated.append(s1);
 for (int i = n1 - 1; i > 0; i--) {
 allRotated.append(s1.substring(i) + s1.substring(0, i));
 }
 // Return true if s2 is a substring of allRotated
 String rotated = allRotated.toString();
 return isSubstring(s2, rotated);
 }
 @Test
 public static void abcTest() {
 String abc = "abc";
 String cab = "cab";
 String bca = "bca";
 assertTrue(isRotation(abc, cab));
 assertTrue(isRotation(abc, bca));
 }
 @Test
 public static void falseTest(){
 String abc = "abc";
 String cba = "cba";
 assertFalse(isRotation(abc,cba));
 }
 @Test
 public static void evenTest(){
 String abcd = "abcd";
 String dcba = "dcba";
 assertFalse(isRotation(abcd,dcba));
 }
 @Test
 public static void identityTest(){
 String aaaa = "aaaa";
 assertTrue(isRotation(aaaa,aaaa));
 }
 public static void main(String[] args) {
 abcTest();
 falseTest();
 evenTest();
 identityTest();
 }
}

• Michael Shaw: Hints: if the runtime of isSubstring is O(n^2), what is n? If you append n strings of length n, how long is the whole string? Are you sure allRotated needs to be that long?

Answer 1

I have a couple of comments on the code that you have posted.

First, your isSubstring function is not checking for a 0 length n1 string, so it will always return true for an empty string - is that what you want?

Second, your isSubstring function is calling s2.substring for every possible position until it finds a match. You can limit the number of calls by performing a simple pre-check to see if s1.charAt(0) == s2.charAt(i). If this is not true, then you know the substring will not match, saving you the overhead of calling the substring() function and creating the additional substring, and then performing the full String.equals() comparison.

Third, your rotation function is overly complex. Since you're just doing an inString comparison, you only have to concatenate the input string to itself once, and then all valid rotations will be a substring of it. To show the example visually, given an input string of "abcd", and the valid rotations of "bcda", "cdab", and "dabc":

abcdabcd
 bcda
 cdab
 dabc

All of the rotations are substrings of the double-concatenated version. This accomplishes the same result of your function, but uses \$O(2n)\$ memory. You originally listed yours as using \$O(n)\$ memory, but that is too low - you are using \$O(n^2)\$ memory, because you are concatenating all the permutations of the rotations.

Finally, your runtime \$O(n^2)\$ calculations aren't quite right, because you are short-circuiting out once you know that the string being searched is too long to be in the remainder. Unless the input string is 1 character, then the number of permutations being checked is actually smaller - and if you add in the first character optimization I listed above, the total cost of the function would go down even further.