How do you check for a string rotation in python?

Question

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.

Nội dung chính Show

Program to check if strings are rotations of each other or not using queue:
How do you check if a String is rotating to another String in Python?
How do you rotate a String in Python?
What is rotation of a String?
Is there a rotate command in Python?

How do you check for a string rotation in python?

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

Read

Discuss

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 other
Input: 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 << "s2 is not a rotation on s1" << endl;

}

else {

vector<int> indexes;

int Size = s1.length();

char firstChar = s1[0];

for (int i = 0; i < Size; i++) {

if (s2[i] == firstChar) {

indexes.push_back(i);

}

bool isRotation = false;

for (int idx : indexes) {

isRotation = checkString(s1, s2, idx, Size);

if (isRotation)

break;

}

if (isRotation)

cout << "Strings are rotations of each other"

<< endl;

else

cout

<< "Strings are not rotations of each other"

<< endl;

}

return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG {

static boolean checkString(String s1, String s2,

int indexFound, int Size)

{

for (int i = 0; i < Size; i++) {

if (s1.charAt(i)

!= s2.charAt((indexFound + i) % Size))

return false;

}

return true;

}

public static void main(String args[])

{

String s1 = "abcd";

String s2 = "cdab";

if (s1.length() != s2.length()) {

System.out.println(

"s2 is not a rotation on s1");

}

else {

ArrayList indexes = new ArrayList<

Integer>();

int Size = s1.length();

char firstChar = s1.charAt(0);

for (int i = 0; i < Size; i++) {

if (s2.charAt(i) == firstChar) {

indexes.add(i);

}

boolean isRotation = false;

for (int idx : indexes) {

isRotation = checkString(s1, s2, idx, Size);

if (isRotation)

break;

}

if (isRotation)

System.out.println(

"Strings are rotations of each other");

else

System.out.println(

"Strings are not rotations of each other");

}

Python3

def checkString(s1, s2, indexFound, Size):

for i in range(Size):

if(s1[i] != s2[(indexFound + i) % Size]):

return False

return True

s1 = "abcd"

s2 = "cdab"

if(len(s1) != len(s2)):

print("s2 is not a rotation on s1")

else:

indexes = []

Size = len(s1)

firstChar = s1[0]

for i in range(Size):

if(s2[i] == firstChar):

indexes.append(i)

isRotation = False

for idx in indexes:

isRotation = checkString(s1, s2, idx, Size)

if(isRotation):

break

if(isRotation):

print("Strings are rotations of each other")

else:

print("Strings are not rotations of each other")

C#

using System;

public class GFG {

public static 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;

}

static public void Main()

{

string s1 = "abcd";

string s2 = "cdab";

if (s1.Length != s2.Length) {

Console.WriteLine("s2 is not a rotation on s1");

}

else {

int[] indexes = new int[1000];

int j = 0;

int Size = s1.Length;

char firstChar = s1[0];

for (int i = 0; i < Size; i++) {

if (s2[i] == firstChar) {

indexes[j] = i;

j++;

}

bool isRotation = false;

for (int idx = 0; idx < indexes.Length; idx++) {

isRotation = checkString(s1, s2, idx, Size);

if (isRotation)

break;

}

if (isRotation)

Console.WriteLine(

"Strings are rotations of each other");

else

Console.WriteLine(

"Strings are not rotations of each other");

}

Javascript

Output

Strings are rotations of each other

Time Complexity: O(n*n) in the worst case, where n is the length of the string.
Auxiliary Space: O(1)

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

Follow the given steps to solve the problem

If the size of both strings is not equal, then it can never be possible.
Push the original string into a queue q1.
Push the string to be checked inside another queue q2.
Keep popping q2‘s and pushing it back into it till the number of such operations is less than the size of the string.
If q2 becomes equal to q1 at any point during these operations, it is possible. Else not.

Below is the implementation of the above approach:

C++

#include

using namespace std;

bool check_rotation(string s, string goal)

{

if (s.size() != goal.size())

return false;

queue<char> q1;

for (int i = 0; i < s.size(); i++) {

q1.push(s[i]);

}

queue<char> q2;

for (int i = 0; i < goal.size(); i++) {

q2.push(goal[i]);

}

int k = goal.size();

while (k--) {

char ch = q2.front();

q2.pop();

q2.push(ch);

if (q2 == q1)

return true;

}

return false;

}

int main()

{

string str1 = "AACD", str2 = "ACDA";

if (check_rotation(str1, str2))

printf("Strings are rotations of each other");

else

printf("Strings are not rotations of each other");

return 0;

}

Java

import java.util.*;

class GFG {

static boolean check_rotation(String s, String goal)

{

if (s.length() != goal.length())

return false;

Queue q1 = new LinkedList<>();

for (int i = 0; i < s.length(); i++) {

q1.add(s.charAt(i));

}

Queue q2 = new LinkedList<>();

for (int i = 0; i < goal.length(); i++) {

q2.add(goal.charAt(i));

}

int k = goal.length();

while (k > 0) {

k--;

char ch = q2.peek();

q2.remove();

q2.add(ch);

if (q2.equals(q1))

return true;

}

return false;

}

public static void main(String[] args)

{

String str1 = "AACD";

String str2 = "ACDA";

if (check_rotation(str1, str2))

System.out.println(

"Strings are rotations of each other");

else

System.out.printf(

"Strings are not rotations of each other");

}

Python3

def check_rotation(s, goal):

if (len(s) != len(goal)):

skip

q1 = []

for i in range(len(s)):

q1.insert(0, s[i])

q2 = []

for i in range(len(goal)):

q2.insert(0, goal[i])

k = len(goal)

while (k > 0):

ch = q2[0]

q2.pop(0)

q2.append(ch)

if (q2 == q1):

return True

k -= 1

return False

if __name__ == "__main__":

string1 = "AACD"

string2 = "ACDA"

if check_rotation(string1, string2):

print("Strings are rotations of each other")

else:

print("Strings are not rotations of each other")

Javascript

Output

Strings are rotations of each other

Time Complexity: O(N1 * N2), where N1 and N2 are the lengths of the strings.
Auxiliary Space: O(N)

Efficient Approach: Follow the given steps to solve the problem

Create a temp string and store concatenation of str1 to str1 in temp, i.e temp = str1.str1
If str2 is a substring of temp then str1 and str2 are rotations of each other.

Example:

str1 = “ABACD”, str2 = “CDABA”
temp = str1.str1 = “ABACDABACD”
Since str2 is a substring of temp, str1 and str2 are rotations of each other.

Below is the implementation of the above approach:

C++

#include

using namespace std;

bool areRotations(string str1, string str2)

{

if (str1.length() != str2.length())

return false;

string temp = str1 + str1;

return (temp.find(str2) != string::npos);

}

int main()

{

string str1 = "AACD", str2 = "ACDA";

if (areRotations(str1, str2))

printf("Strings are rotations of each other");

else

printf("Strings are not rotations of each other");

return 0;

}

C

#include

int areRotations(char* str1, char* str2)

{

int size1 = strlen(str1);

int size2 = strlen(str2);

char* temp;

void* ptr;

if (size1 != size2)

return 0;

temp = (char*)malloc(sizeof(char) * (size1 * 2 + 1));

temp[0] = ' ';

strcat(temp, str1);

ptr = strstr(temp, str2);

free(temp);

if (ptr != NULL)

return 1;

else

return 0;

}

int main()

{

char* str1 = "AACD";

char* str2 = "ACDA";

if (areRotations(str1, str2))

printf("Strings are rotations of each other");

else

printf("Strings are not rotations of each other");

getchar();

return 0;

}

Java

class StringRotation {

static boolean areRotations(String str1, String str2)

{

return (str1.length() == str2.length())

&& ((str1 + str1).indexOf(str2) != -1);

}

public static void main(String[] args)

{

String str1 = "AACD";

String str2 = "ACDA";

if (areRotations(str1, str2))

System.out.println(

"Strings are rotations of each other");

else

System.out.printf(

"Strings are not rotations of each other");

}

Python3

def areRotations(string1, string2):

size1 = len(string1)

size2 = len(string2)

temp = ''

if size1 != size2:

return 0

temp = string1 + string1

if (temp.count(string2) > 0):

return 1

else:

return 0

if __name__ == "__main__":

string1 = "AACD"

string2 = "ACDA"

if areRotations(string1, string2):

print("Strings are rotations of each other")

else:

print("Strings are not rotations of each other")

C#

using System;

class GFG {

static bool areRotations(String str1, String str2)

{

return (str1.Length == str2.Length)

&& ((str1 + str1).IndexOf(str2) != -1);

}

public static void Main()

{

String str1 = "FGABCDE";

String str2 = "ABCDEFG";

if (areRotations(str1, str2))

Console.Write("Strings are"

+ " rotation s of each other");

else

Console.Write("Strings are "

+ "not rotations of each other");

}

PHP

function areRotations($str1, $str2)

{

if (strlen($str1) != strlen($str2))

{

return false;

}

$temp = $str1.$str1;

if(strpos($temp, $str2) != false)

{

return true;

}

else

{

return false;

}

$str1 = "AACD";

$str2 = "ACDA";

if (areRotations($str1, $str2))

{

echo "Strings are rotations ".

"of each other";

}

else

{

echo "Strings are not " .

"rotations of each other" ;

}

?>

`Javascript`

Output

Strings are rotations of each other

Time Complexity: O(N), where N is the length of the string. Auxiliary Space: O(N)

 
How do you check if a String is rotating to another String in Python?
(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.
How do you rotate a String in Python?
Approach is very simple, Separate string in two parts first & second, for Left rotation Lfirst = str[0 : d] and Lsecond = str[d :]. For Right rotation Rfirst = str[0 : len(str)-d] and Rsecond = str[len(str)-d : ]. Now concatenate these two parts second + first accordingly.
What is rotation of a String?
A String is said to be a rotation of another String, if it has the same length, contains the same characters, and they were rotated around one of the characters. For example, String"bcda" is a rotation of "abcd" but "bdca" is not a rotation of String "abcd".
Is there a rotate command in Python?
rotate is undoable, NOT queryable, and NOT editable. The rotate command is used to change the rotation of geometric objects. The rotation values are specified as Euler angles (rx, ry, rz).
...
.

programming python String rotation LeetCode 38 Permutation in string String::npos

How do you check for a string rotation in python?

C++

Java

Python3

C#

Javascript

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

C++

Java

Python3

Javascript

C++

C

Java

Python3

C#

PHP

Javascript

How do you check if a String is rotating to another String in Python?

How do you rotate a String in Python?

What is rotation of a String?

Is there a rotate command in Python?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội

`Javascript`