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

Dadas dos strings, la tarea es encontrar si se puede obtener una string rotando otra string dos lugares. 

Ejemplos: 

Entrada : string1 = «amazon», string2 = «azonam» 
Salida: Sí 
// girado en sentido antihorario
Entrada : string1 = «amazon», string2 = «onamaz» 
Salida : Sí 
// girado en sentido horario

Preguntado en : Amazon Entrevista

A continuación se muestra la implementación del enfoque anterior.

// C++ program to check if a string is two time
// rotation of another string.
#include<bits/stdc++.h>
using namespace std;
 
// Function to check if string2 is obtained by
// string 1
bool isRotated(string str1, string str2)
{
    if (str1.length() != str2.length())
        return false;
    if(str1.length()<2){
      return str1.compare(str2) == 0;
    }
    string clock_rot = "";
    string anticlock_rot = "";
    int len = str2.length();
 
    // Initialize string as anti-clockwise rotation
    anticlock_rot = anticlock_rot +
                    str2.substr(len-2, 2) +
                    str2.substr(0, len-2) ;
 
    // Initialize string as clock wise rotation
    clock_rot = clock_rot +
                str2.substr(2) +
                str2.substr(0, 2) ;
 
    // check if any of them is equal to string1
    return (str1.compare(clock_rot) == 0 ||
            str1.compare(anticlock_rot) == 0);
}
 
// Driver code
int main()
{
    string str1 = "geeks";
    string str2 = "eksge";
 
    isRotated(str1, str2) ? cout << "Yes"
                          : cout << "No";
    return 0;
}

// Java program to check if a string is two time
// rotation of another string.
 
class Test
{
    // Method to check if string2 is obtained by
    // string 1
    static boolean isRotated(String str1, String str2)
    {
        if (str1.length() != str2.length())
            return false;
        if(str1.length() < 2)
        {
            return str1.equals(str2);
        }
      
        String clock_rot = "";
        String anticlock_rot = "";
        int len = str2.length();
      
        // Initialize string as anti-clockwise rotation
        anticlock_rot = anticlock_rot +
                        str2.substring(len-2, len) +
                        str2.substring(0, len-2) ;
      
        // Initialize string as clock wise rotation
        clock_rot = clock_rot +
                    str2.substring(2) +
                    str2.substring(0, 2) ;
      
        // check if any of them is equal to string1
        return (str1.equals(clock_rot) ||
                str1.equals(anticlock_rot));
    }
     
    // Driver method
    public static void main(String[] args)
    {
        String str1 = "geeks";
        String str2 = "eksge";
      
        System.out.println(isRotated(str1, str2) ?  "Yes"
                              : "No");
    }
}

# Python 3 program to check if a string
# is two time rotation of another string.
 
# Function to check if string2 is
# obtained by string 1
def isRotated(str1, str2):
 
    if (len(str1) != len(str2)):
        return False
     
    if(len(str1) < 2):
        return str1 == str2
    clock_rot = ""
    anticlock_rot = ""
    l = len(str2)
 
    # Initialize string as anti-clockwise rotation
    anticlock_rot = (anticlock_rot + str2[l - 2:] +
                                     str2[0: l - 2])
     
    # Initialize string as clock wise rotation
    clock_rot = clock_rot + str2[2:] + str2[0:2]
 
    # check if any of them is equal to string1
    return (str1 == clock_rot or
            str1 == anticlock_rot)
 
# Driver code
if __name__ == "__main__":
     
    str1 = "geeks"
    str2 = "eksge"
if isRotated(str1, str2):
    print("Yes") 
else:
    print("No")
 
# This code is contributed by ita_c

using System;
 
// C# program to check if a string is two time
// rotation of another string.
 
public class Test {
    // Method to check if string2 is obtained by
    // string 1
    public static bool isRotated(string str1, string str2)
    {
        if (str1.Length != str2.Length) {
            return false;
        }
 
        if (str1.Length < 2) {
            return str1.Equals(str2);
        }
 
        string clock_rot = "";
        string anticlock_rot = "";
        int len = str2.Length;
 
        // Initialize string as anti-clockwise rotation
        anticlock_rot
            = anticlock_rot
              + str2.Substring(len - 2, len - (len - 2))
              + str2.Substring(0, len - 2);
 
        // Initialize string as clock wise rotation
        clock_rot = clock_rot + str2.Substring(2)
                    + str2.Substring(0, 2);
 
        // check if any of them is equal to string1
        return (str1.Equals(clock_rot)
                || str1.Equals(anticlock_rot));
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        string str1 = "geeks";
        string str2 = "eksge";
 
        Console.WriteLine(isRotated(str1, str2) ? "Yes"
                                                : "No");
    }
}
 
// This code is contributed by Shrikant13

<script>
 
// Javascript program to check if a
// string is two time rotation of
// another string.
     
// Method to check if string2 is
// obtained by string 1
function isRotated(str1, str2)
{
    if (str1.length != str2.length)
        return false;
         
    if (str1.length < 2)
    {
        return str1.localeCompare(str2);
    }
   
    let clock_rot = "";
    let anticlock_rot = "";
    let len = str2.length;
   
    // Initialize string as anti-clockwise rotation
    anticlock_rot = anticlock_rot +
                    str2.substring(len - 2, len + 1) +
                    str2.substring(0, len - 1) ;
   
    // Initialize string as clock wise rotation
    clock_rot = clock_rot +
                str2.substring(2, str2.length - 2 + 1) +
                str2.substring(0, 2 + 1);
   
    // Check if any of them is equal to string1
    return (str1.localeCompare(clock_rot) ||
            str1.localeCompare(anticlock_rot));
}
 
// Driver code
let str1 = "geeks";
let str2 = "eksge";
 
document.write(isRotated(str1, str2) ? 
               "Yes" : "No");
 
// This code is contributed by rag2127
 
</script>

Yes

Complejidad temporal : O(n) 
Espacio auxiliar: O(n)

Ejercicio: compruebe si string2 se obtiene al rotar string1 k lugares

Método 2: sin usar ningún espacio adicional: 

Podríamos verificar directamente si la cuerda gira o no comparando las dos cuerdas. 

Pasos –

1. Compruebe si la cuerda gira en el sentido de las agujas del reloj.
2. Compruebe si la cuerda gira en sentido contrario a las agujas del reloj. 
3. Devuelve verdadero si alguno de los anteriores es verdadero

Comparamos en sentido horario y antihorario usando bucles for y el operador de módulo:

Tenga en cuenta que – 

Para el sentido de las agujas del reloj – str1[i] == str2[(i + 2) % n]

Para el sentido contrario a las agujas del reloj: str1[(i + 2) % n] == str2[i]

Aquí n es la longitud de la string 

¡Compruebe usando las dos condiciones anteriores y el problema se resolverá!

Ver el código para una mejor comprensión.

// C++ code to find if string is rotated by 2 positions
 
#include <iostream>
using namespace std;
 
bool isRotated(string str1, string str2)
{
    // Your code here
    // clockwise direction check
    int n = str1.length();
    bool clockwise = true, anticlockwise = true;
    for (int i = 0; i < n; i++)
    {
        if (str1[i] != str2[(i + 2) % n])
        {
            clockwise = false; // not rotated clockwise
            break;
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        if (str1[(i + 2) % n] != str2[i])
        {
            anticlockwise = false; // not rotated anticlockwise
            break;
        }
    }
 
    return clockwise or anticlockwise; // if any of both is true, return true
}
int main()
{
    string str1 = "geeks";
    string str2 = "eksge";
 
    isRotated(str1, str2) ? cout << "Yes"
                          : cout << "No";
    return 0;
}
 
//code contributed by Anshit Bansal

Yes

Complejidad de tiempo – O(n)
Complejidad de espacio – O(1)

Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.