Programa de Python para eliminar recursivamente todos los duplicados adyacentes

Dada una string, elimine recursivamente los caracteres duplicados adyacentes de la string. La string de salida no debe tener duplicados adyacentes. Vea los siguientes ejemplos.

Ejemplos :

Entrada : azxxzy
Salida : ay
Primero, “axxxzy” se reduce a “azzy”.
La string «azzy» contiene duplicados,
por lo que se reduce aún más a «ay».

Entrada : geeksforgeeg
Salida : gksfor
Primero, “geeksforgeeg” se reduce a
“gksforgg”. La string «gksforgg»
contiene duplicados, por lo que se
reduce aún más a «gksfor».

Entrada : caaabbbaacdddd
Salida : String vacía

Entrada : acaaabbbacdddd
Salida : acac

Se puede seguir el siguiente enfoque para eliminar duplicados en tiempo O(N) :

Comience desde el carácter más a la izquierda y elimine los duplicados en la esquina izquierda si hay alguno.
El primer carácter debe ser diferente de su adyacente ahora. Recur para string de longitud n-1 (string sin primer carácter).
Deje que la string obtenida después de reducir la substring derecha de longitud n-1 sea rem_str . Hay tres casos posibles
1. Si el primer carácter de rem_str coincide con el primer carácter de la string original, elimine el primer carácter de rem_str .
2. Si la string restante se vacía y el último carácter eliminado es el mismo que el primer carácter de la string original. Devuelve una string vacía.
3. De lo contrario, agregue el primer carácter de la string original al comienzo de rem_str .
Devuelve rem_str .

La imagen de abajo es una ejecución en seco del enfoque anterior:

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

Python

# Python program to remove all 
# adjacent duplicates from a string
  
# Recursively removes adjacent 
# duplicates from str and returns
# new string. las_removed is a 
# pointer to last_removed character
def removeUtil(string, last_removed):
  
    # If length of string is 1 or 0
    if len(string) == 0 or len(string) == 1:
        return string
  
    # Remove leftmost same characters 
    # and recur for remaining 
    # string
    if string[0] == string[1]:
        last_removed = ord(string[0])
        while len(string) > 1 and 
                  string[0] == string[1]:
            string = string[1:]
        string = string[1:]
  
        return removeUtil(string, last_removed)
  
    # At this point, the first 
    # character is definiotely different
    # from its adjacent. Ignore first 
    # character and recursively 
    # remove characters from remaining string
    rem_str = removeUtil(string[1:], 
                         last_removed)
  
    # Check if the first character 
    # of the rem_string matches 
    # with the first character of 
    # the original string
    if len(rem_str) != 0 and 
           rem_str[0] == string[0]:
        last_removed = ord(string[0])
        return (rem_str[1:])
  
    # If remaining string becomes 
    # empty and last removed character
    # is same as first character of 
    # original string. This is needed
    # for a string like "acbbcddc"
    if len(rem_str) == 0 and 
       last_removed == ord(string[0]):
        return rem_str
  
    # If the two first characters of 
    # str and rem_str don't match, 
    # append first character of str 
    # before the first character of 
    # rem_str.
    return ([string[0]] + rem_str)
  
def remove(string):
    last_removed = 0
    return toString(removeUtil(toList(string), 
                               last_removed))
  
# Utility functions
def toList(string):
    x = []
    for i in string:
        x.append(i)
    return x
  
def toString(x):
    return ''.join(x)
  
# Driver program
string1 = "geeksforgeeg"
print remove(string1)
  
string2 = "azxxxzy"
print remove(string2)
  
string3 = "caaabbbaac"
print remove(string3)
  
string4 = "gghhg"
print remove(string4)
  
string5 = "aaaacddddcappp"
print remove(string5)
  
string6 = "aaaaaaaaaa"
print remove(string6)
  
string7 = "qpaaaaadaaaaadprq"
print remove(string7)
  
string8 = "acaaabbbacdddd"
print remove(string8)
  
string9 = "acbbcddc"
print remove(string9)
# This code is contributed by BHAVYA JAIN

Producción:

gksfor
ay
g
a
qrq
acac
a

Complejidad de tiempo: la complejidad de tiempo de la solución se puede escribir como T(n) = T(nk) + O(k) donde n es la longitud de la string de entrada y k es el número de primeros caracteres que son iguales. La solución de la recurrencia es O(n)

Gracias a Prachi Bodke por sugerir este problema y la solución inicial.

Consulte el artículo completo sobre Eliminación recursiva de todos los duplicados adyacentes para obtener más detalles.

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

Python

Deja una respuesta Cancelar la respuesta