Decode String

+10

Una cadena codificada escribe el texto repetido como k[text]: text escrito k veces seguidas. Los grupos pueden anidarse, así que 2[a3[b]] representa abbbabbb. Dada una cadena codificada s, devuelve la cadena decodificada.

Las letras que están fuera de todos los corchetes permanecen igual. Cada cantidad es un número entero positivo escrito justo antes de su [, y los dígitos no aparecen en ningún otro lugar.

Función

decodeString(s: string) → string

sstring: la cadena codificada
Devuelvestring: la cadena decodificada

Restricciones

1 ≤ s.length ≤ 10⁴
s contiene solo letras inglesas minúsculas, dígitos, [ y ].
s es una codificación válida: cada [ va después de un recuento y tiene un ] correspondiente, y ningún corchete está vacío.
Cada cantidad k cumple 1 ≤ k ≤ 300 y no tiene ceros iniciales.
Los corchetes pueden anidarse hasta 100 niveles de profundidad.
La cadena decodificada tiene como máximo 5 × 10⁴ caracteres.

Ejemplos

Entrada: s = "2[ab]3[c]x"
Salida: "ababcccx"
Explicación: 2[ab] da abab y 3[c] da ccc. La x está fuera de todos los corchetes y se copia tal cual: ababcccx.

Entrada: s = "2[x3[yz]]"
Salida: "xyzyzyzxyzyzyz"
Explicación: Primero decodifica el interior: 3[yz] es yzyzyz, así que el cuerpo exterior es xyzyzyz. Escrito dos veces, es xyzyzyzxyzyzyz.

Entrada: s = "q10[w]e"
Salida: "qwwwwwwwwwwe"
Explicación: El recuento es 10, leído a partir de dos dígitos, así que w aparece diez veces entre q y e.

Para ir más allá

La cadena decodificada puede ser mucho más larga que la entrada. ¿Cómo devolverías el carácter en la posición i sin construir la cadena, cuando su longitud puede llegar a 10^18?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

No puedes escribir las copias de un grupo hasta que conozcas su cuerpo, y el cuerpo puede contener más grupos. Por eso, todos los enfoques terminan primero los grupos más internos: reescriben la cadena de adentro hacia afuera, recurren en cada cuerpo o mantienen los grupos exteriores sin terminar en una pila. Aquí n es la longitud de la entrada, m la longitud decodificada y d la profundidad de anidamiento.

Expande el grupo más interno y luego repite

Intuición

Encuentra un grupo que no tenga ningún grupo dentro, escribe sus copias en su lugar y vuelve a buscar. El primer ] siempre cierra un grupo así: ningún grupo se ha cerrado antes, así que su contenido no tiene corchetes. Su [ es el más cercano a su izquierda, y la cantidad es la secuencia de dígitos que aparece antes. En 2[x3[yz]], 3[yz] se expande primero, dando 2[xyzyzyz], y una expansión más da la respuesta.

Cada expansión reconstruye toda la cadena. Con b grupos y una salida de m caracteres, eso supone hasta b × m copias: 1,000 grupos que se decodifican en 50,000 caracteres significan hasta 5 × 10^7.

Algoritmo

Encuentra el primer ]. Si no hay ninguno, devuelve la cadena.
Avanza hacia la izquierda hasta el [ más cercano. El texto entre ambos es el cuerpo.
Lee los dígitos anteriores a ese [ como el recuento k.
Reemplaza todo desde el primer dígito hasta el ] por el cuerpo escrito k veces, y repite.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Descenso recursivo

Intuición

Una cadena codificada es una secuencia de letras y grupos, y el contenido de un grupo también es una cadena codificada. Así que una función, decode, lee desde una posición compartida hasta llegar a un ] o al final de la entrada, y se llama a sí misma para leer el contenido de cada grupo. Esa llamada se detiene en el ] correspondiente, porque cada ] más profundo fue consumido por una llamada más profunda. Para 2[x3[yz]], la llamada más interna devuelve yz, la intermedia xyzyzyz y la externa escribe eso dos veces.

Cada carácter de entrada se lee una vez, pero cada carácter de salida se copia una vez por cada grupo que lo contiene: tiempo O(n + m·d). La recursión alcanza una profundidad de d llamadas.

Algoritmo

Mantén una posición pos, compartida por todas las llamadas, que empieza en 0.
decode() hace un bucle mientras pos esté dentro de la cadena y no esté en un ].
Si es una letra, añádela y continúa.
Si es un dígito, lee el número entero k, omite el [, llama a decode() para el cuerpo, omite el ] y añade el cuerpo k veces.
Devuelve lo que se ha construido. La primera llamada devuelve la cadena decodificada.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

Una pasada con una pila

Intuición

La recursión mantiene una parte de texto sin terminar por cada grupo abierto en sus marcos de llamada. Guarda esas partes en tu propia pila y la decodificación se convierte en un solo bucle. Un [ guarda el texto decodificado hasta el momento en este nivel, junto con su contador, y comienza el cuerpo desde vacío. Un ] los extrae y agrega las copias al texto guardado. Los grupos se cierran en el orden inverso al que se abren, así que la parte superior de la pila siempre es el nivel al que vuelve un ].

En 2[x3[yz]] apilas (vacío, 2) y luego (x, 3). El primer ] extrae (x, 3) y current se convierte en xyzyzyz; el último extrae (vacío, 2) y lo duplica. El trabajo se corresponde con la recursión, O(n + m·d), pero el anidamiento profundo hace crecer una lista, no la pila de llamadas.

Algoritmo

Empieza con una pila vacía, un current vacío y count = 0.
Al encontrar un dígito, establece count = count × 10 + digit.
Al encontrar [, apila (current, count) y luego restablece ambos.
Al encontrar una letra, añádela a current.
Al encontrar ], desapila (before, k) y establece current en before seguido de k copias de current.
Devuelve current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

Errores comunes y casos límite

Leer un solo dígito como si fuera todo el número de repeticiones. En q10[w]e el número de repeticiones es 10; tomar solo el dígito anterior a [ repite w 0 veces.
No restablecer count a 0 después de guardarlo. Entonces, los dígitos del siguiente grupo se añaden al número anterior, por lo que 2[a3[b]] interpreta el número de repeticiones interno como 23.
Poner las copias antes del texto guardado. ab2[c] es abcc, no ccab.
Omitir las letras del nivel superior. La x en 2[ab]3[c]x debe estar en la respuesta.
Añadir un carácter a la vez a una cadena inmutable. Cada añadido puede copiar toda la cadena, así que una respuesta de 50,000 caracteres requiere más de mil millones de copias de caracteres. Recopila las partes en una lista o en un constructor de cadenas.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Decode String?

Leer la entrada es O(n). Cada carácter de salida se copia una vez por cada grupo que lo rodea, así que el total es O(n + m·d), donde m es la longitud decodificada y d la profundidad de anidamiento. Cuando cada cantidad es al menos 2, las copias se mantienen por debajo de 2m. Ningún método supera O(m), porque la respuesta tiene m caracteres.

¿Deberías resolver Decode String con recursión o con una pila?

Ambos realizan el mismo trabajo. La recursión sigue directamente el formato, ya que el cuerpo de un grupo es en sí mismo una cadena codificada, y suele ser la forma más rápida de escribirlo. La versión con pila se ejecuta en un solo bucle y mantiene los niveles sin terminar en una lista, por lo que una entrada anidada con miles de niveles de profundidad no puede desbordar la pila de llamadas.

¿Cómo manejas los conteos con más de un dígito?

Construye el número a medida que lo lees: empieza en 0 y, por cada dígito, establece count = count × 10 + digit. Cuando llega [, el número está completo, así que 300[a] da 300.

def decodeString(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "2[ab]3[c]x"

Salida Esperada

"ababcccx"

Decode String

Función

Restricciones

Ejemplos

Pistas

Solución

Expande el grupo más interno y luego repite

Descenso recursivo

Una pasada con una pila

Errores comunes y casos límite

Preguntas frecuentes3

Problemas similares