Programa Javascript para verificar 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:  

<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)

Enfoque: en este enfoque, usamos una string temporal que es una string larga con una multiplicidad de str1 por 2. Si queremos rotar la string por d lugar, cortamos la string desde n lugares comenzando desde d. De manera similar, rotamos a la derecha. Para la rotación a la derecha, usamos d con valor (longitud de str1) – d. 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:  

<script>
 
// 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;
     
    // Making temp to slice the rotated string
    var temp = str1 + str1;
    var temp2 = str2 + str2;
 
    // Index to slice the string to give rotation
    var len = str1.length
    var pos1 = len - d  ;
     
    // Slicing the string
    var left_rot_str1 = temp.slice(d, d + len)
    var right_rot_str2 = temp2.slice(pos1, pos1+len );
        
    // Flags check equality of roation of string to both the string
    var flag = left_rot_str1 == str2 ;
    var flag2 = right_rot_str2 == str1;
      
     // Returing
    if(flag || flag2) 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))
    console.log("Yes");
else
    console.log("No");
</script>

Producción:

Yes 

¡ Consulte el artículo completo sobre Comprobar si se puede obtener una string rotando otra string d lugares para obtener más detalles!