Compruebe si se puede obtener una string rotando otra string d lugares

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:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to reverse an array from left
// index to right index (both inclusive)
void ReverseArray(string& arr, int left, int right)
{
    char temp;
    while (left < right) {
        temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}
 
// Function that returns true if str1 can be
// made equal to str2 by rotating either
// d places to the left or to the right
bool RotateAndCheck(string& str1, string& str2, int d)
{
 
    if (str1.length() != str2.length())
        return false;
 
    // Left Rotation string will contain
    // the string rotated Anti-Clockwise
    // Right Rotation string will contain
    // the string rotated Clockwise
    string left_rot_str1, right_rot_str1;
    bool left_flag = true, right_flag = true;
    int str1_size = str1.size();
 
    // Copying the str1 string to left rotation string
    // and right rotation string
    for (int i = 0; i < str1_size; i++) {
        left_rot_str1.push_back(str1[i]);
        right_rot_str1.push_back(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 (int i = 0; i < str1_size; i++) {
 
        // 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 || right_flag)
        return true;
    return false;
}
 
// Driver code
int main()
{
 
    string str1 = "abcdefg";
    string str2 = "cdefgab";
 
    // d is the rotating factor
    int d = 2;
 
    // In case length of str1 < d
    d = d % str1.size();
 
    if (RotateAndCheck(str1, str2, d))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

# 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

using System;
 
// C# program to check if a string is two time
// rotation of another string.
public class Test {
 
  static string ReverseArray(char[] arr, int left, int right)
  {
    char temp;
    while (left < right) {
      temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
    return String.Join("",arr);
  }
 
  // Method to check if string2 is obtained by
  // string 1
  public static bool RotateAndCheck(string str1, string str2, int d)
  {
    if (str1.Length != str2.Length) {
      return false;
    }
 
    // Left Rotation string will contain
    // the string rotated Anti-Clockwise
    // Right Rotation string will contain
    // the string rotated Clockwise
    string left_rot_str1="", right_rot_str1="";
    bool left_flag = true, right_flag = true;
    int len1 = str1.Length;
 
    // Copying the str1 string to left rotation string
    // and right rotation string
    for (int i = 0; i < len1; i++) {
      left_rot_str1+=str1[i];
      right_rot_str1+=str1[i];
    }
 
    // Rotating the string d positions to the left
    left_rot_str1=ReverseArray(left_rot_str1.ToCharArray(), 0, d - 1);
    left_rot_str1=ReverseArray(left_rot_str1.ToCharArray(), d, len1 - 1);
    left_rot_str1=ReverseArray(left_rot_str1.ToCharArray(), 0, len1 - 1);
 
    // Rotating the string d positions to the right
    right_rot_str1=ReverseArray(right_rot_str1.ToCharArray(), 0, len1 - d - 1);
    right_rot_str1=ReverseArray(right_rot_str1.ToCharArray(), len1 - d, len1 - 1);
    right_rot_str1=ReverseArray(right_rot_str1.ToCharArray(), 0, len1 - 1);
 
    // Comparing the rotated strings
    for (int i = 0; i < len1; i++) {
 
      // 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 || right_flag)
      return true;
    return false;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    string str1 = "abcdefg";
    string str2 = "cdefgab";
 
    // d is the rotating factor
    int d = 2;
 
    // In case length of str1 < d
    d = d % str1.Length;
 
    Console.WriteLine(RotateAndCheck(str1, str2,d) ? "Yes"
                      : "No");
  }
}
 
// This code is contributed by Aarti_Rathi

<script>
 
// JavaScript implementation of the approach
 
// Function to reverse an array from left
// index to right index (both inclusive)
function ReverseArray(arr, left, right)
{
    var temp;
    while (left < right)
    {
        temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}
 
// Function that returns true if str1 can be
// made equal to str2 by rotating either
// d places to the left or to the right
function RotateAndCheck(str1, str2, d)
{
    if (str1.length !== str2.length)
        return false;
     
    // Left Rotation string will contain
    // the string rotated Anti-Clockwise
    // Right Rotation string will contain
    // the string rotated Clockwise
    var left_rot_str1 = [];
    var right_rot_str1 = [];
    var left_flag = true,
    right_flag = true;
    var str1_size = str1.length;
     
    // Copying the str1 string to left rotation string
    // and right rotation string
    for(var i = 0; i < str1_size; i++)
    {
        left_rot_str1.push(str1[i]);
        right_rot_str1.push(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(var i = 0; i < str1_size; i++)
    {
        // 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 || right_flag)
        return true;
         
    return false;
}
 
// Driver code
var str1 = "abcdefg";
var str2 = "cdefgab";
 
// d is the rotating factor
var d = 2;
 
// In case length of str1 < d
d = d % str1.length;
 
if (RotateAndCheck(str1, str2, d))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by rdtank
 
</script>

Yes

Complejidad de tiempo: O(n), donde n representa el tamaño de la string.
Espacio auxiliar: O(n), donde n representa el tamaño de la string.