Given two strings, the task is to find if a string can be obtained by rotating another string two places.
Examples:
Input: string1 = “amazon”, string2 = “azonam”
Output: Yes
// rotated anti-clockwise
Input: string1 = “amazon”, string2 = “onamaz”
Output: Yes
// rotated clockwise
Asked in: Amazon Interview
1- There can be only two cases:
a) Clockwise rotated
b) Anti-clockwise rotated
2- If clockwise rotated that means elements
are shifted in right.
So, check if a substring[2.... len-1] of
string2 when concatenated with substring[0,1]
of string2 is equal to string1. Then, return true.
3- Else, check if it is rotated anti-clockwise
that means elements are shifted to left.
So, check if concatenation of substring[len-2, len-1]
with substring[0....len-3] makes it equals to
string1. Then return true.
4- Else, return false.
Below is the implementation of the above approach.
Java
// Java program to check if a string// is two time rotation of another string.class Test{ // Method to check if string2 is // obtained by string 1 static boolean isRotated(String str1, String str2) { if (str1.length() != str2.length()) return false; if(str1.length() < 2) { return str1.equals(str2); } String clock_rot = ""; String anticlock_rot = ""; int len = str2.length(); // Initialize string as anti-clockwise // rotation anticlock_rot = anticlock_rot + str2.substring(len-2, len) + str2.substring(0, len-2) ; // Initialize string as clock wise // rotation clock_rot = clock_rot + str2.substring(2) + str2.substring(0, 2) ; // check if any of them is equal to string1 return (str1.equals(clock_rot) || str1.equals(anticlock_rot)); } // Driver method public static void main(String[] args) { String str1 = "geeks"; String str2 = "eksge"; System.out.println(isRotated(str1, str2) ? "Yes" : "No"); }} |
Output:
Yes
Time Complexity: O(n), where n is the size of the given string.
Auxiliary Space: O(n) because using extra space
Please refer complete article on Check if a string can be obtained by rotating another string 2 places for more details!