Programa Python3 para verificar si una string se puede formar a partir de otra string con un máximo de X cambios circulares en el sentido de las agujas del reloj

Dado un entero X y dos strings S1 y S2 , la tarea es comprobar que la string S1 se puede convertir en la string S2 cambiando los caracteres circularmente en el sentido de las agujas del reloj como máximo X veces.

Entrada: S1 = “abcd”, S2 = “dddd”, X = 3 
Salida: Sí 
Explicación: 
La string dada S1 se puede convertir en la string S2 como 
: Carácter “a” – Cambiar 3 veces – “d” 
Carácter “b” – Desplazar 2 veces – “d” 
Carácter “c” – Desplazar 1 vez – “d” 
Carácter “d” – Desplazar 0 veces – “d”

Entrada: S1 = “usted”, S2 = “ara”, X = 6 
Salida: Sí 
Explicación: 
La string dada S1 se puede convertir en la string S2 como – 
Carácter “y” – Desplazamiento circular 2 veces – “a” 
Carácter “o” – Desplazamiento 3 veces – “r” 
Carácter “u” – Desplazamiento circular 6 veces – “a”  

Enfoque: La idea es recorrer la string y para cada índice y encontrar la diferencia entre los valores ASCII del carácter en los índices respectivos de las dos strings. Si la diferencia es menor que 0, entonces para un desplazamiento circular, suma 26 para obtener la diferencia real. Si para cualquier índice, la diferencia excede X , entonces S2 no se puede formar a partir de S1 , de lo contrario es posible. 
A continuación se muestra la implementación del enfoque anterior: 

# Python3 implementation to check
# that the given string can be
# converted to another string 
# by circular clockwise shift
  
# Function to check that the 
# string s1 can be converted
# to s2 by clockwise circular
# shift of all characters of 
# str1 atmost X times
def isConversionPossible(s1, s2, x):
    n = len(s1)
    s1 = list(s1)
    s2 = list(s2)
      
    for i in range(n):
          
        # Difference between the 
        # ASCII numbers of characters
        diff = ord(s2[i]) - ord(s1[i])
          
        # If both characters 
        # are the same
        if diff == 0:
            continue
          
        # Condition to check if the 
        # difference less than 0 then
        # find the circular shift by 
        # adding 26 to it
        if diff < 0:
            diff = diff + 26
        # If difference between 
        # their ASCII values
        # exceeds X
        if diff > x:
            return False
      
    return True
      
  
# Driver Code
if __name__ == "__main__":
    s1 = "you"
    s2 = "ara"
    x = 6
      
    # Function Call
    result = isConversionPossible(s1, s2, x)
      
    if result:
        print("YES")
    else:
        print("NO")

YES

Complejidad de tiempo: O(N),N=Longitud(S1)

Espacio Auxiliar: O(1)

¡ Consulte el artículo completo sobre Comprobar si se puede formar una string a partir de otra string con un máximo de X cambios circulares en el sentido de las agujas del reloj para obtener más detalles!