Dadas dos strings str1 y str2 y un entero d , la tarea es verificar si str2 se puede obtener rotando str1 por d lugares (hacia la izquierda o hacia la derecha).
Ejemplos:
Entrada: str1 = “abcdefg”, str2 = “cdefgab”, d = 2
Salida: Sí
Rotar str1 2 lugares a la izquierda.Entrada: str1 = “abcdefg”, str2 = “cdfdawb”, d = 6
Salida: No
Enfoque: Aquí se ha discutido un enfoque para resolver el mismo problema . En este artículo, el algoritmo de inversión se utiliza para rotar la string hacia la izquierda y hacia la derecha en O(n). Si alguna de las rotaciones de str1 es igual a str2 , imprima Sí ; de lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 implementation of the approach
# Function to reverse an array from left
# index to right index (both inclusive)
def ReverseArray(arr, left, right) :
while (left < right) :
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left += 1;
right -= 1;
# Function that returns true if str1 can be
# made equal to str2 by rotating either
# d places to the left or to the right
def RotateAndCheck(str1, str2, d) :
if (len(str1) != len(str2)) :
return False;
# Left Rotation string will contain
# the string rotated Anti-Clockwise
# Right Rotation string will contain
# the string rotated Clockwise
left_rot_str1 = []; right_rot_str1 = [];
left_flag = True; right_flag = True;
str1_size = len(str1);
# Copying the str1 string to left rotation string
# and right rotation string
for i in range(str1_size) :
left_rot_str1.append(str1[i]);
right_rot_str1.append(str1[i]);
# Rotating the string d positions to the left
ReverseArray(left_rot_str1, 0, d - 1);
ReverseArray(left_rot_str1, d, str1_size - 1);
ReverseArray(left_rot_str1, 0, str1_size - 1);
# Rotating the string d positions to the right
ReverseArray(right_rot_str1, 0, str1_size - d - 1);
ReverseArray(right_rot_str1,
str1_size - d, str1_size - 1);
ReverseArray(right_rot_str1, 0, str1_size - 1);
# Comparing the rotated strings
for i in range(str1_size) :
# If cannot be made equal with left rotation
if (left_rot_str1[i] != str2[i]) :
left_flag = False;
# If cannot be made equal with right rotation
if (right_rot_str1[i] != str2[i]) :
right_flag = False;
# If both or any one of the rotations
# of str1 were equal to str2
if (left_flag or right_flag) :
return True;
return False;
# Driver code
if __name__ == "__main__" :
str1 = list("abcdefg");
str2 = list("cdefgab");
# d is the rotating factor
d = 2;
# In case length of str1 < d
d = d % len(str1);
if (RotateAndCheck(str1, str2, d)) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
Yes
Complejidad de tiempo: O(n), donde n representa el tamaño de la string dada.
Espacio auxiliar: O(n), donde n representa el tamaño de la string dada.
¡ Consulte el artículo completo sobre Comprobar si se puede obtener una string rotando otra string d lugares para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA