Dadas dos strings s1 y s2. La tarea es averiguar el número mínimo de rotaciones de string para la string dada s1 para obtener la string real s2.
Ejemplos:
Input : eeksg, geeks Output: 1 Explanation: g is rotated left to obtain geeks. Input : eksge, geeks Output: 2 Explanation : e and g are left rotated to obtain geeks.
Acercarse:
- Use el corte de cuerdas para rotar la cuerda.
- Realice rotaciones a la derecha
str1=str1[1:len(str1)]+str1[0]en la string para obtener la string real. - Realice rotaciones a la izquierda
m=m[len(m)-1]+m[:len(m)-1]en la string para obtener la string real. - Imprime el mínimo de rotaciones izquierda (x) y derecha (y).
COMPLEJIDAD DE TIEMPO: O(n)
A continuación se muestra la implementación:
def findRotations(str1, str2):
# To count left rotations
# of string
x = 0
# To count right rotations
# of string
y = 0
m = str1
while True:
# left rotating the string
m = m[len(m)-1] + m[:len(m)-1]
# checking if rotated and
# actual string are equal.
if(m == str2):
x += 1
break
else:
x += 1
if x > len(str2) :
break
while True:
# right rotating the string
str1 = str1[1:len(str1)]+str1[0]
# checking if rotated and actual
# string are equal.
if(str1 == str2):
y += 1
break
else:
y += 1
if y > len(str2):
break
if x < len(str2):
# printing the minimum
# number of rotations.
print(min(x,y))
else:
print("given strings are not of same kind")
# Driver code
findRotations('sgeek', 'geeks')
Producción:
1
Publicación traducida automáticamente
Artículo escrito por MANIKANTA2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA