POTD Solutions | 14 Nov’23 | Check if strings are rotations of each other or not
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of String but will also help you build up problem-solving skills.
POTD 14 November: Check if strings are rotations of each other or not
You are given two strings of equal lengths, s1 and s2. The task is to check if s2 is a rotated version of the string s1.
Note: The characters in the strings are in lowercase.
Examples:
Input: s1 = “w3wiki”, s2 = “forBeginnerBeginner”
Output: 1
Explanation:
s1 is w3wiki, s2 is forBeginnerBeginner. Clearly, s2 is a rotated version of s1 as s2 can be obtained by left-rotating s1 by 5 units.Input: s1 = “mightandmagic”, s2=”andmagicmigth”
Output: 0
Explanation: Here with any amount of rotation s2 can’t be obtained by s1.
Check if strings are rotations of each other or not using Strings:
The idea is to create a temp string and store the concatenation of s1 to s1 in temp, i.e temp = s1+s1. Check if s2 is a substring of temp then s1 and s2 are rotations of each other.
Illustration:
s1 = “ABACD”, s2 = “CDABA”
temp = s1.s1 = “ABACDABACD”
Since s2 is a substring of temp, s1 and s2 are rotations of each other.
Below is the implementation of the above approach:
C++
class Solution { public : // Function to check if two strings are rotations of // each other or not. bool areRotations(string s1, string s2) { // if s1 and s2 are unequal then it is not possoble // to get one from other by rotation. if (s1.length() != s2.length()) return false ; // concatenating s1 with s2 string temp = s1 + s1; // check if s2 is substring of temp or not return (temp.find(s2) != string::npos); } }; |
Java
class Solution { // Function to check if two strings are rotations of // each other or not. public static boolean areRotations(String s1, String s2) { // There lengths must be same and str2 must be // a substring of str1 concatenated with str1. return (s1.length() == s2.length()) && ((s1 + s1).indexOf(s2) != - 1 ); } } |
Python3
class Solution: # Function to check if two strings are rotations of each other or not. def areRotations( self , s1, s2): size1 = len (s1) size2 = len (s2) temp = '' # Check if sizes of two strings are same if size1 ! = size2: return 0 # Create a temp string with value str1.str1 temp = s1 + s1 # Now check if str2 is a substring of temp # string.count returns the number of occurrences of # the second string in temp if (temp.count(s2) > 0 ): return 1 else : return 0 |
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N)