def isRotation[s1, s2]:
return len[s1] == len[s2] and s2 in s1*2
isRotation["ABCD", "CDAB"]
>> True
The code above was given as one of many ways to check if two strings are a rotation of each other. However, I don't understand why String1[s1] has to be multiplied by 2 in the code.
asked Feb 15, 2021 at 12:38
1
In python, multiplying strings is repeating the string, for example:
>>> 'abc'*2
'abcabc'
>>> 'abc'*4
'abcabcabcabc'
So in order to know if a string is a rotation of another string, you would need to multiplie it by 2, for example:
>>> 'bca' in 'abc'
False
>>> 'bca' in 'abc' * 2
True
answered Feb 15, 2021 at 12:43
Roy CohenRoy Cohen
1,4901 gold badge4 silver badges21 bronze badges
Multiplying a string by 2 will double the original string. And because s1 wraps around, regardless of its starting position the whole string can be found somewhere within twice its length
ABCDABCD
|||| DABC
||| CDAB
|| BCDA
| ABCD
answered Feb 15, 2021 at 12:43
Reti43Reti43
9,4453 gold badges26 silver badges44 bronze badges
Rotating a string is as good as chopping it at point of rotation and putting that chopped part at the end of string.
ABCDEFGH rotated 4 places to left is:
- Chop at 4-> ABCD EFGH
- Place at the end -> EFGHABCD
Python str*x gives you str concatenated to itself x times.
>>> a = 'String'
>>> a*2
'StringString'
>>>
Putting these two points together with the fact that any string can be rotated by maximum amount equal to its length [when it becomes the original string] gives you the logic to check the rotated string's presence in str*2.
answered Feb 15, 2021 at 12:48
lllrnr101lllrnr101
2,1782 gold badges3 silver badges14 bronze badges
Understanding of your question is- To compare a string with the rotation string.
My approach to address the same would be.
1- To get the rotation string.
def rotate_str[strg, n]:
return strg[n:] + strg[:n]
length = 2 #can change this to whatever value suits to you or even pass this as arg.
print[rotate['SAMPLE', length]]
2- compare strings.
str1 = 'SAMPLE'
str2 = rotate[str1, length]
def compare_str[str1, str2]:
return str1 == str2
answered Feb 15, 2021 at 14:10
mkranamkrana
4024 silver badges10 bronze badges
Here when we multiply s1 with 2. It returns s1s1 like if s1="ABCD", it will return "ABCDABCD", and in if s2 in s1*2 we are checking that if "CRAB" is in "ABCDABCD" which is true.
answered Feb 15, 2021 at 12:46
View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
Given a string s1 and a string s2, write a function to check whether s2 is a rotation of s1.
Examples:
Input: S1 = ABCD, S2 = CDAB
Output: Strings are rotations of each otherInput: S1 = ABCD, S2 = ACBD
Output: Strings are not rotations of each other
Naive Approach: Follow the given steps to solve the problem
- Find all the positions of the first character of the original string in the string to be checked.
- For every position found, consider it to be the starting index of the string to be checked.
- Beginning from the new starting index, compare both strings and check whether they are equal or not.
- [Suppose the original string to is s1, string to be checked to be s2,n is the length of strings and j is the position of the first character of s1 in s2, then for i < [length of original string] , check if s1[i]==s2[[j+1]%n]. Return false if any character mismatch is found, else return true.
- Repeat 3rd step for all positions found.
Below is the implementation of the above approach:
C++
#include
using namespace std;
bool checkString[string& s1, string& s2, int indexFound,
int Size]
{
for [int i = 0; i < Size; i++] {
if [s1[i] != s2[[indexFound + i] % Size]]
return false;
}
return true;
}
int main[]
{
string s1 = "abcd";
string s2 = "cdab";
if [s1.length[] != s2.length[]] {
cout
Javascript
function areRotations[ str1, str2]
{
return
[str1.length == str2.length] &&
[[str1 + str1].indexOf[str2] != -1];
}
var str1 = "AACD";
var str2 = "ACDA";
if [areRotations[str1, str2]]
document.write["Strings are rotations of each other"];
else
document.write["Strings are not rotations of each other"];
Output
Strings are rotations of each other
Time Complexity: O[N], where N is the length of the string.
Auxiliary Space: O[N]