Dada una string, necesitamos encontrar el número mínimo de rotaciones requeridas para obtener la misma string.
Ejemplos:
Input : s = "geeks" Output : 5 Input : s = "aaaa" Output : 1
La idea se basa en la siguiente publicación.
Un programa para verificar si las strings son rotaciones entre sí o no.
- Paso 1: Inicializar resultado = 0 (Aquí el resultado es el conteo de rotaciones)
- Paso 2: tome una string temporal igual a la string original concatenada consigo misma.
- Paso 3: ahora tome la substring de la string temporal del mismo tamaño que la string original a partir del segundo carácter (o índice 1).
- Paso 4: Aumente el conteo.
- Paso 5: compruebe si la substring se vuelve igual a la string original. Si es así, entonces rompa el bucle. De lo contrario, vaya al paso 2 y repítalo desde el siguiente índice.
Implementación:
C++
// C++ program to determine minimum number
// of rotations required to yield same
// string.
#include <iostream>
using namespace std;
// Returns count of rotations to get the
// same string back.
int findRotations(string str)
{
// tmp is the concatenated string.
string tmp = str + str;
int n = str.length();
for (int i = 1; i <= n; i++) {
// substring from i index of original
// string size.
string substring = tmp.substr(i, str.size());
// if substring matches with original string
// then we will come out of the loop.
if (str == substring)
return i;
}
return n;
}
// Driver code
int main()
{
string str = "abc";
cout << findRotations(str) << endl;
return 0;
}
Java
// Java program to determine minimum number
// of rotations required to yield same
// string.
import java.util.*;
class GFG
{
// Returns count of rotations to get the
// same string back.
static int findRotations(String str)
{
// tmp is the concatenated string.
String tmp = str + str;
int n = str.length();
for (int i = 1; i <= n; i++)
{
// substring from i index of original
// string size.
String substring = tmp.substring(
i, i+str.length());
// if substring matches with original string
// then we will come out of the loop.
if (str.equals(substring))
return i;
}
return n;
}
// Driver Method
public static void main(String[] args)
{
String str = "aaaa";
System.out.println(findRotations(str));
}
}
/* This code is contributed by Mr. Somesh Awasthi */
Python3
# Python 3 program to determine minimum # number of rotations required to yield # same string. # Returns count of rotations to get the # same string back. def findRotations(str): # tmp is the concatenated string. tmp = str + str n = len(str) for i in range(1, n + 1): # substring from i index of # original string size. substring = tmp[i: i+n] # if substring matches with # original string then we will # come out of the loop. if (str == substring): return i return n # Driver code if __name__ == '__main__': str = "abc" print(findRotations(str)) # This code is contributed # by 29AjayKumar.
C#
// C# program to determine minimum number
// of rotations required to yield same
// string.
using System;
class GFG {
// Returns count of rotations to get
// the same string back.
static int findRotations(String str)
{
// tmp is the concatenated string.
String tmp = str + str;
int n = str.Length;
for (int i = 1; i <= n; i++)
{
// substring from i index of
// original string size.
String substring =
tmp.Substring(i, str.Length);
// if substring matches with
// original string then we will
// come out of the loop.
if (str == substring)
return i;
}
return n;
}
// Driver Method
public static void Main()
{
String str = "abc";
Console.Write(findRotations(str));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to determine minimum
// number of rotations required to
// yield same string.
// Returns count of rotations
// to get the same string back.
function findRotations($str)
{
// tmp is the concatenated string.
$tmp = ($str + $str);
$n = strlen($str);
for ( $i = 1; $i <= $n; $i++)
{
// substring from i index
// of original string size.
$substring = $tmp.substr($i,
strlen($str));
// if substring matches with
// original string then we will
// come out of the loop.
if ($str == $substring)
return $i;
}
return $n;
}
// Driver code
$str = "abc";
echo findRotations($str), "\n";
// This code is contributed
// by Sachin
?>
Javascript
<script>
// javascript program to determine minimum number
// of rotations required to yield same
// string.
// Returns count of rotations to get the
// same string back.
function findRotations( str) {
// tmp is the concatenated string.
var tmp = str + str;
var n = str.length;
for (var i = 1; i <= n; i++) {
// substring from i index of original
// string size.
var substring = tmp.substring(i ,str.length);
// if substring matches with original string
// then we will come out of the loop.
if (str===(substring))
return i;
}
return n;
}
// Driver Method
var str = "abc";
document.write(findRotations(str));
// This code contributed by gauravrajput1
</script>
Producción
3
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar : O(n)
Podemos resolver este problema sin usar ninguna variable temporal como espacio extra. Recorreremos la string original y en cada posición la dividiremos y concatenaremos la substring derecha y la substring izquierda y verificaremos si es igual a la string original
Implementación:
C++
// C++ program to determine minimum number
// of rotations required to yield same
// string.
#include <iostream>
using namespace std;
// Returns count of rotations to get the
// same string back.
int findRotations(string str)
{
int ans = 0; //to store the answer
int n = str.length(); //length of the string
//All the length where we can partition
for(int i=1;i<n-1;i++)
{
//right part + left part = rotated string
// we are checking whether the rotated string is equal to
//original string
if(str.substr(i,n-i) + str.substr(0,i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
// Driver code
int main()
{
string str = "abc";
cout << findRotations(str) << endl;
return 0;
}
Java
// Java program to determine minimum number
// of rotations required to yield same
// string.
import java.util.*;
class GFG
{
// Returns count of rotations to get the
// same string back.
static int findRotations(String str)
{
int ans = 0; //to store the answer
int n = str.length(); //length of the string
//All the length where we can partition
for(int i=1;i<str.length()-1;i++)
{
//right part + left part = rotated string
// we are checking whether the rotated string is equal to
//original string
if(str.substring(i, str.length()-i) + str.substring(0, i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
// Driver Method
public static void main(String[] args)
{
String str = "abc";
System.out.println(findRotations(str));
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python program to determine minimum number # of rotations required to yield same # string. # Returns count of rotations to get the # same string back. def findRotations(Str): ans = 0 # to store the answer n = len(Str) # length of the String # All the length where we can partition for i in range(1 , len(Str) - 1): # right part + left part = rotated String # we are checking whether the rotated String is equal to # original String if(Str[i: n] + Str[0: i] == Str): ans = i break if(ans == 0): return n return ans # Driver code Str = "abc" print(findRotations(Str)) # This code is contributed by shinjanpatra
C#
// C# program to determine minimum number
// of rotations required to yield same
// string.
using System;
class GFG {
// Returns count of rotations to get
// the same string back.
static int findRotations(String str)
{
int ans = 0; //to store the answer
int n = str.Length; //length of the string
//All the length where we can partition
for(int i=1;i<str.Length-1;i++)
{
//right part + left part = rotated string
// we are checking whether the rotated string is equal to
//original string
if(str.Substring(i,n-i) + str.Substring(0,i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
// Driver Method
public static void Main()
{
String str = "abc";
Console.Write(findRotations(str));
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// JavaScript program to determine minimum number
// of rotations required to yield same
// string.
// Returns count of rotations to get the
// same string back.
function findRotations(str)
{
let ans = 0; // to store the answer
let n = str.length; // length of the string
// All the length where we can partition
for(let i = 1; i < str.length - 1; i++)
{
// right part + left part = rotated string
// we are checking whether the rotated string is equal to
// original string
if(str.substr(i, n - i) + str.substr(0, i) == str)
{
ans = i;
break;
}
}
if(ans == 0)
return n;
return ans;
}
// Driver code
let str = "abc";
document.write(findRotations(str),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
3
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Implementación alternativa en Python:
C++
// C++ program to determine minimum
// number of rotations required to yield
// same string.
#include <iostream>
using namespace std;
// Driver program
int main()
{
string String = "aaaa";
string check = "";
for(int r = 1; r < String.length() + 1; r++)
{
// checking the input after each rotation
check = String.substr(0, r) + String.substr(r, String.length()-r);
// following if statement checks if input is
// equals to check , if yes it will print r and
// break out of the loop
if(check == String){
cout<<r;
break;
}
}
return 0;
}
// This code is contributed by shinjanpatra
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void main (String[] args) {
String string = "aaaa";
String check = "";
for(int r = 1; r < string.length() + 1; r++)
{
// checking the input after each rotation
check = string.substring(0, r) + string.substring(r, string.length());
// following if statement checks if input is
// equals to check , if yes it will print r and
// break out of the loop
if(check.equals(string)){
System.out.println(r);
break;
}
}
}
}
Python3
# Python 3 program to determine minimum # number of rotations required to yield # same string. # input string = 'aaaa' check = '' for r in range(1, len(string)+1): # checking the input after each rotation check = string[r:] + string[:r] # following if statement checks if input is # equals to check , if yes it will print r and # break out of the loop if check == string: print(r) break # This code is contributed # by nagasowmyanarayanan.
C#
// C# program to determine minimum number
// of rotations required to yield same
// string.
using System;
class GFG {
// Driver Method
public static void Main()
{
String str = "aaaa";
String check = "";
for(int r = 1; r < str.Length + 1; r++)
{
// checking the input after each rotation
check = str.Substring(0, r) + str.Substring(r, str.Length-r);
// following if statement checks if input is
// equals to check , if yes it will print r and
// break out of the loop
if(check == str){
Console.Write(r);
break;
}
}
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// JavaScript program to determine minimum
// number of rotations required to yield
// same string.
// input
let string = 'aaaa'
let check = ''
for(let r=1;r<string.length+1;r++){
// checking the input after each rotation
check = string.substring(r) + string.substring(0,r)
// following if statement checks if input is
// equals to check , if yes it will print r and
// break out of the loop
if(check == string){
document.write(r)
break
}
}
// This code is contributed
// by shinjanpatra
</script>
Producción
1
Complejidad de tiempo: O(n 2 ), n como longitud de string
Espacio auxiliar: O(n), n como longitud de string
Este artículo es una contribución de Aarti_Rathi Jatin Goyal . 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.
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