Program to check if strings are rotations of each other or not

Question

Please review my code for above problem. I tried to cover the maximum possible boundary condition. Any optimizations or new easy and fast solution are welcome.

public class CheckStringAreRotationalyEquals {
 private static boolean areRotaionalyEquals(String s1, String s2) {
 boolean areRotaionalyEquals = Boolean.FALSE;
 int i = 0, j = 0;
 if ((s1 == null && s2 == null)) {
 areRotaionalyEquals = Boolean.TRUE;
 } else {
 if (s1 != null && s2 != null) {
 // if both the strings are not null then check for
 // are they rotaionaly equals
 if (s1.isEmpty() && s2.isEmpty()) {
 areRotaionalyEquals = Boolean.TRUE;
 } else if (s1.length() == s2.length()) {
 char ch2 = s2.charAt(j);
 boolean match = Boolean.TRUE;
 int count = 0;
 for (i = 0; i < s1.length(); i++) {
 char ch1 = s1.charAt(i);
 if (ch1 == ch2) {
 j++;
 count++;
 if (j != s2.length()) {
 ch2 = s2.charAt(j);
 }
 }
 }
 // check for the remaining character present in the s2 and
 // start it to matched with the s1
 if (j != s2.length()) {
 ch2 = s2.charAt(j);
 for (int k = 0; k < i - j; k++) {
 char ch1 = s1.charAt(k);
 if (ch1 == ch2) {
 j++;
 count++;
 if (j != s2.length()) {
 ch2 = s2.charAt(j);
 }
 } else {
 match = Boolean.FALSE;
 break;
 }
 }
 }
 // if all the character matches of both the strings
 // sequentially then return TRUE else FALSE
 if (j == count && match) {
 areRotaionalyEquals = Boolean.TRUE;
 } else {
 areRotaionalyEquals = Boolean.FALSE;
 }
 }
 }
 }
 return areRotaionalyEquals;
 }
 public static void main(String[] args) {
 System.out.println("The two strings are rotionaly equals => ");
 String s1 = "nullpointer";
 String s2 = "ternullpoin";
 boolean result = areRotaionalyEquals(s1, s2);
 System.out.println(result);
 s1 = "nullpointer";
 s2 = "interponull";
 result = areRotaionalyEquals(s1, s2);
 System.out.println(result);
 s1 = "nullpointer";
 s2 = "rnullpointe";
 result = areRotaionalyEquals(s1, s2);
 System.out.println(result);
 result = areRotaionalyEquals("", "");
 System.out.println(result);
 result = areRotaionalyEquals("", "ternullpoin");
 System.out.println(result);
 result = areRotaionalyEquals(null, "");
 System.out.println(result);
 result = areRotaionalyEquals("", null);
 System.out.println(result);
 result = areRotaionalyEquals(null, null);
 System.out.println(result);
 result = areRotaionalyEquals("hodor", "orhod");
 System.out.println(result);
 result = areRotaionalyEquals("sh", "hs");
 System.out.println(result);
 result = areRotaionalyEquals("persistent", "tentpersis");
 System.out.println(result);
 result = areRotaionalyEquals("persistent", "tentsisper");
 System.out.println(result);
 result = areRotaionalyEquals("ternullpoin", "ternullpoin");
 System.out.println(result);
 }
}

Answer 1

The code can greatly be simplified by using a different algorithm.

Note : two string are rotationally equal if the concatenation of one and itself contains the other.

"tuallyperpe" -> "tuallyperpetuallyper" contains "perpetually"

So a quick implementation would be :

public boolean rotationallyEqual(String s1, String s2) {
 if (s1 == s2) {
 return true;
 }
 if (s1 == null || s2 == null || s1.length() != s2.length()) {
 return false;
 }
 return (s1 + s1).contains(s2);
}

Answer 2

• The code is not correct. It claims that "aba" and "aab" are not rotationally equal, which is obviously wrong. The reason is that it looks only for the very first occurrence in s1 of an initial character of s2.

• Flat is better than nested. Prefer an early return.

• The

   if (j == count && match) {
   areRotaionalyEquals = Boolean.TRUE;
   } else {
   areRotaionalyEquals = Boolean.FALSE;
   }
  

  is a long way to say

   areRotaionalyEquals = ((j == count) && match);
  

  I also recommend an explicit parenthesis around the comparison.

• Dair: Shift "aba" by one you get "aab". How are they not rotationally equivalent?
• vnp: @Dair Of course they are. The program says they are not. That's my point.
• Dair: my b. Sorry about that.

Answer 3

To expand on @vnp's point:

Flat is better than nested. Prefer an early return.

You put a lot of corner cases in middle of the main logic. Finish them off early on so someone reading your code doesn't have their train of thought messed up. (Also, just return out):

 if ((s1 == null && s2 == null)) {
 return Boolean.TRUE;
 } else if ((s1 == null || s2 == null)) {
 return Boolean.FALSE;
 } else if (s1.isEmpty() && s2.isEmpty()) {
 return Boolean.TRUE;
 } else {
 ...

This will reduce the nesting substantially.

Answer 4

Continuing from @Dair and @vnp's answers, here's some more tips.

Unnecessary auto-unboxing

The return type of the method is a primitive boolean yet you always store (or after the refactorings up till now return) a boxed Boolean (notice the capital B). These should be replaced with return true and return false instead.

if/else vs if/return

If you have an if return construction like this, you don't need to write an else:

if (s1 == null && s2 == null) {
 return true;
}
if(s1 == null || s2 == null) {
 return false;
}
if(s1.isEmpty()){
 return s2.isEmpty();
}
if(s1.length() != s2.length()){
 return false;
}
int i = 0;
...

I find this slightly more readable than the if/else structure, and it saves you 1 level of indentation after the last if/return.

comments are bad

I'm not talking about javadoc explaining what a method does without going into the implementation details, or comments explaining why something is done a certain way. I'm talking about comments that tell you what some code does. The code itself should tell you what it does. If it doesn't, that usually means you should refactor the code until it does.

One of the main problems here are the variable names.

meaningful variable names

The variables s1, s2, ch1 and ch2 are good enough. Anyone would guess that these represent the 2 strings and a specific char in those strings.

The variables i and j on the other hand don't really work. This is because they are also used outside of the loops. I suggest to at least rename i to offSetS1 for example to point out that this is the offset of the first string to wich the second matches (when looped around).

At least then it becomes obvious that the first for loop looks for an offset between the 2 strings.

serious bug

Now that we got those things out of the way let's look at where your code is wrong (like @vnp already pointed out). And how to fix it.

The easiest way to write this method correctly is to just concatenate s1 to itself and then check if it contains s2:

private static boolean areRotaionalyEquals(String s1, String s2) {
 if(s1 == null) {
 return s2 == null;
 }
 return (s1 + s1).contains(s2);
}

But that's too elegant for us so let's fix the slightly more memory efficient (is it?) implementation that only stores 2 extra chars and some ints while checking the rotational equality.

First let's describe the algorithm on a high level:

For each offset in s1 {
 check if s1 starting at this offset and looping around is equal to s2
 if so, return true, else continue loop
}
return false; (no match found)

Or translated to java code:

private static boolean areRotaionalyEquals(String s1, String s2) {
 if (s1 == null && s2 == null) {
 return true;
 }
 if (s1 == null || s2 == null) {
 return false;
 }
 if (s1.isEmpty()) {
 return s2.isEmpty();
 }
 if (s1.length() != s2.length()) {
 return false;
 }
 for(int offsetS1 = 0; offset < s1.length(); offsetS1++){
 int currentIndex1 = offset;
 for(int currentIndex2 = 0; currentIndex2 < s2.length(); currentIndex2 ++){
 if (s1.charAt(currentIndex1) != s2.charAt(currentIndex2)) {
 break;
 }
 currentIndex1 = (currentIndex1+1) % s1.length();
 if(currentIndex1==offsetS1){
 return true;
 }
 }
 }
 return false;
}

Oops, did I just post a corrected version of your code? I usually don't intend to answer broken code, but this one was just too interesting to pass up on :)

Answer 5

Just a quick addition: fix the typos by writing rotationally.