Learn-dsa..in 30 days!



























CC-10 : Check if one String is rotation of another String.

Description:

A String is said to be rotated by 1 position right if the character at position 1 moves to position 2, original character at position 2 moves to position 3, original character at position 3 moves to position 4 and so on. The original character at last position moves to position 1.

A String is said to be rotated by 2 positions right if the character at position 1 moves to position 3, original character at position 2 moves to position 4, original character at position 3 moves to position 5 and so on. The original character at last position moves to position 2. The original character at second last position moves to position 1.

The same logic can be applied for rotation of n positions. Given two input Strings str1 and str2, if str2 is a rotation of str1 return true, else return false.

Test cases and expected outputs:

Input Parameters Expected outputs
str1="This is a sentence";
str2="eThis is a sentenc"; 		str2 is rotation of str1.
str1="This is a sentence";
str2="a sentenceThis is "; 		str2 is rotation of str1.
str1="This is a sentence";
str2="This is a sentence"; 		str2 is rotation of str1. (0 rotation).
str1="This is a sentence";
str2="This is another sentence"; 		str2 is *not* rotation of str1.

Pseudocode:

The java method should accept following input parameters: str1 (String), str2 (String).
Initialize char array chars1=str1.toCharArray().
Initialize char array chars2=str2.toCharArray().
If length of str1 and str2 are not of same length, they cannot be rotations of each other, so return false from the program.
Initialize boolean variable s2Found=””; we will use variable to keep track if sequence of characters of chars2 that match chars2.
Iterate through chars2 using for loop using s2idx as loop variable, starting from index 0 and incrementing s2idx till we reach chars2.length-1:
If chars[s2idx] == chars1[0], we may have found the start character of chars1 in chars2:
Save current s2idx in s2Check integer variable.
We will start from s2Check and check if all next characters of chars2 are same as chars1. This will help us to know if chars2 is a rotation of chars1 from position s2Idx onwards.
Iterate through chars1 using for loop using s1idx as loop variable, starting from index 0 and incrementing s1idx till we reach chars1.length-1:
If chars1[s1idx] != chars2[s2Check] then the rotation sequence does not match, break current iteration and continue search for first character using outer loop.
If chars1[s1idx] != chars2[s2Check]:
Increment s2Check by 1.
If s2Check== char2.length-1, it means we have reached the end of chars2 and we need to continue rotation checking from index 0 of chars2. So set s2Check to 0.
If (s1Idx==chars1.length) this means we have checked all characters in chars1 and they exist in correct rotated sequence in chars2. So set s2Found to true.
When inner loop is completed and s2Found is true, it means we have found the chars2 is a rotation of chars1, so there is no further need to check further in outer loop, so we can break out of outer loop as well.
When out loop completes if s2Found variable is true it means it means we have found the chars2 is a rotation of chars1, so return true from the program. If s2Found is false, it means we have found the chars2 is a *not* rotation of chars1, so return false from the program.

The above algorithm can also be completed using Java String APIs:

If length of str1 and str2 are not of same length, they cannot be rotations of each other, so return false from the program.
Set String str3=str1+str1; str3 now contains str1 twice.
Using String.contains() method check if str3 contains str2:
If str3 contains str2. It means str2 is a rotation of str1 so return true from the program.
If str3 does not contain str2. It means str2 is a *not* rotation of str1 so return false from the program.

Code:

public boolean stringCheckS1S2Rotation(String str1, String str2) {
	char[] chars1=str1.toCharArray();
	char[] chars2=str2.toCharArray();
	if (chars1.length != chars2.length) {
		return false;
	}
	boolean s2Found=false;
	for (int s2Idx=0; s2Idx < chars2.length; s2Idx++) {
		if (chars2[s2Idx]==chars1[0]) {
			int s2Check=s2Idx;
			for(int s1Idx=0; s1Idx < chars1.length; s1Idx++) {
				if (chars1[s1Idx] != chars2[s2Check]) {
					s2Found=false;
					break;
				}else {
					s2Check++;
					if (s2Check==chars2.length) {
						s2Check=0;
					}
					if (s1Idx==chars1.length-1) {
						s2Found=true;
					}
				}
			}
			if (s2Found==true) {
				break;
			}
		}
	}
	
	return s2Found;
}
public boolean stringCheckS1S2RotationwithAPI(String str1, String str2) {
	if (str1.length() != str2.length()) {
		return false;
	}
	String str3=str1+str1;
	if (str3.contains(str2)) {
		return true;
	}else {	
		return false;
	}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us