Decode String
Una cadena codificada representa texto repetido como k[text], que significa que text se escribe k veces seguidas. Los grupos pueden estar dentro de otros grupos, así que 2[a3[b]] significa abbbabbb. Escribe una función que reciba una cadena codificada s y devuelva la cadena decodificada.
Las letras que están fuera de todos los corchetes se mantienen tal como están. Cada contador es un número entero positivo escrito justo antes de su [, y los dígitos no aparecen en ningún otro lugar.
Función
- sstring
- la cadena codificada
- Devuelvestring
- la cadena decodificada
Restricciones
1 ≤ s.length ≤ 104scontiene solo letras minúsculas del alfabeto inglés, dígitos,[y].ses una codificación válida: cada[va seguido de un recuento y tiene un]correspondiente, y ningún corchete está vacío.- Cada cantidad
ksatisface1 ≤ k ≤ 300y no tiene ceros iniciales. - Los corchetes pueden anidarse hasta 100 niveles de profundidad.
- La cadena decodificada tiene como máximo
5 × 104caracteres.
Ejemplos
- Entrada
- s = "2[ab]3[c]x"
- Salida
- "ababcccx"
- Explicación
2[ab]daababy3[c]daccc. Laxestá fuera de todos los corchetes, así que se copia tal cual, lo que daababcccx.
- Entrada
- s = "2[x3[yz]]"
- Salida
- "xyzyzyzxyzyzyz"
- Explicación
- Decodifica primero el interior:
3[yz]esyzyzyz, así que el cuerpo del grupo exterior esxyzyzyz. Escrito dos veces, quedaxyzyzyzxyzyzyz.
- Entrada
- s = "q10[w]e"
- Salida
- "qwwwwwwwwwwe"
- Explicación
- El conteo es
10, leído como dos dígitos, así quewaparece diez veces entreqye. El código que lee solo el dígito junto a[lo repetiría 0 veces.
+22 pruebas ocultas al enviar
Para ir más allá
La cadena decodificada puede ser mucho más larga que la entrada. ¿Cómo devolverías únicamente el carácter en la posición i de la cadena decodificada, sin construirla, cuando la longitud decodificada puede alcanzar 10^18?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
No puedes escribir
3[...]hasta que sepas qué hay dentro de los corchetes, y dentro puede haber más grupos. ¿Qué tipo de grupo puedes descodificar siempre de inmediato?Un grupo que no contiene ningún otro grupo se puede expandir de una vez, así que trabaja desde dentro hacia fuera. Cuando llega un
], el grupo que cierra está completo, y necesitas el texto y el recuento que estaban esperando antes de su[.Recorre la cadena una vez, conservando el texto construido hasta el momento y el número que se está leyendo. Al encontrar
[, apila ambos y empieza de nuevo. Al encontrar], sácalos de la pila y añade el texto actual, repetido, al texto que sacaste. Construye cada número dígito a dígito para que funcionen10y300.
Solución
El recuento va antes de los corchetes, pero no puedes escribir las copias hasta saber qué hay dentro de ellos, y dentro puede haber más grupos. Por eso, un grupo solo se puede expandir cuando todos los grupos que contiene están terminados. Cada uno de los siguientes enfoques permite terminar primero los grupos más internos: reescribir la cadena desde dentro hacia fuera, dejar que una llamada recursiva termine el grupo interno antes que el externo o mantener los grupos externos sin terminar en una pila. A continuación, n es la longitud de la entrada, m la longitud de la cadena decodificada y d el anidamiento más profundo.
Expande el grupo más interno y luego repite
Intuición
Decodifica la cadena como lo harías en papel. Encuentra un grupo que no tenga ningún otro grupo dentro, escribe sus copias en su lugar y vuelve a mirar. En 2[x3[yz]], el grupo 3[yz] no tiene nada dentro, así que la cadena se convierte en 2[xyzyzyz], y una expansión más da la respuesta.
El primer ] de la cadena siempre cierra un grupo de este tipo. Ningún otro grupo se ha cerrado antes, así que entre ese ] y su [ no puede haber ningún corchete. Ese [ es el más cercano a su izquierda, y el contador es la secuencia de dígitos justo delante. Sustituye el contador, los corchetes y el contenido por el contenido escrito k veces, y repite hasta que no quede ningún ].
Esto es correcto, pero cada expansión reconstruye toda la cadena. Con b grupos y una cadena que crece hasta acercarse a m caracteres, eso supone hasta b × m copias de caracteres. La prueba oculta con unos 1,300 grupos uno junto a otro requiere unas 25 millones de copias para producir 27,688 caracteres, mientras que bastaría con recorrer la entrada una sola vez.
Algoritmo
- Busca el primer
]en la cadena. Si no hay ninguno, la cadena está decodificada: devuélvela. - Desde ahí, avanza hacia la izquierda hasta el
[más cercano. El texto entre ellos es el contenido del grupo. - Avanza más hacia la izquierda sobre los dígitos anteriores a ese
[y léelos como el contadork. - Reemplaza todo desde el primer dígito hasta
]por el contenido escritokveces. - Vuelve al paso 1.
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
El formato es recursivo: una cadena codificada es una secuencia de letras y grupos, y el cuerpo de un grupo también es una cadena codificada. Así que escribe una función, decode, que lea desde una posición compartida hasta llegar a ], que termina su nivel, o al final de la entrada, y devuelva lo que leyó, decodificado.
Cuando decode encuentra un dígito, lee el número entero, salta [ y se llama a sí misma para decodificar el cuerpo. Esa llamada se detiene en el ] correspondiente, porque cualquier ] más profundo ya fue consumido por una llamada más profunda. La función que hizo la llamada salta ], añade el cuerpo k veces y sigue leyendo. Para 2[x3[yz]], la llamada externa lee 2; la siguiente llamada lee x y 3; una tercera llamada devuelve yz; la llamada intermedia devuelve xyzyzyz; y la externa lo escribe dos veces.
Cada carácter de la entrada se lee una vez. El costo real está en las copias: un carácter de la salida se copia una vez por cada grupo que lo rodea, así que el tiempo es O(n + m·d) para una profundidad de anidamiento d. La recursión también llega a una profundidad de d llamadas. Eso está bien para 100 niveles, pero una entrada muy profunda puede desbordar la pila de llamadas: Python, por ejemplo, se detiene en 1,000 llamadas anidadas de forma predeterminada.
Algoritmo
- Mantén una posición
pos, compartida por cada llamada, que comience en el primer carácter. decode()repite mientrasposesté 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 adecode()para el contenido, omite el]y añade el contenidokveces. - Devuelve lo que se haya 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, dentro de sus marcos de llamada. Puedes guardar esas partes en una pila propia y leer la cadena en un solo bucle.
Lleva el registro de dos cosas para el nivel actual: current, el texto decodificado hasta ahora, y count, el número que se está leyendo. Un dígito amplía count como count × 10 + digit, de modo que 10 y 300 se obtienen correctamente. Un [ abre un nivel: apila current y count, y luego reinicia ambos. Una letra se añade a current. Un ] cierra el nivel: desapila el texto y el número guardados, y current pasa a ser el texto guardado seguido de count copias de current.
Sigue el proceso con 2[x3[yz]]. En el primer [, apilas (vacío, 2). La x hace que current sea igual a x. En el segundo [, apilas (x, 3), y yz llena un current nuevo. El primer ] desapila (x, 3), así que current pasa a ser xyzyzyz. El último ] desapila (vacío, 2), y current pasa a ser xyzyzyzxyzyzyz.
Los grupos se cierran en el orden inverso al que se abren, así que la cima de la pila siempre corresponde al nivel al que vuelve el ]. El trabajo es equivalente al de la recursión, O(n + m·d), pero el anidamiento profundo solo hace crecer una lista, nunca la pila de llamadas.
Algoritmo
- Empieza con una pila vacía, un
currentvacío ycount = 0. - Al encontrar un dígito, establece
count = count × 10 + digit. - Al encontrar
[, inserta el par (current,count) en la pila; después, restablececurrenta vacío ycounta 0. - Al encontrar una letra, añádela a
current. - Al encontrar
], extrae (before,k) y establececurrentenbeforeseguido dekcopias decurrent. - Después del último carácter, 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
La mayoría de las respuestas incorrectas se deben a leer mal el conteo o a dónde va el texto guardado.
- Leer un dígito como si fuera todo el conteo. En
q10[w]e, el conteo es 10. El código que toma solo el dígito anterior a[repitew0 veces. - Olvidarse de restablecer
counta 0 después de apilarlo. Entonces, los dígitos del siguiente grupo se suman al número anterior, así que2[a3[b]]lee el conteo interno como 23. - Poner las copias antes del texto guardado. Al llegar a un
], el resultado es el texto anterior al grupo seguido de las copias, así queab2[c]esabcc, noccab. - Perder letras en el nivel superior. La
xde2[ab]3[c]xestá fuera de todos los corchetes y aun así debe formar parte de la respuesta. - Agregar un carácter a la vez a una cadena inmutable larga. Cada agregado puede copiar toda la cadena, lo que convierte una respuesta de 50,000 caracteres en miles de millones de copias. Recopila las partes en una lista o en un constructor de cadenas.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Decode String?
Leer la entrada es O(n). Construir la salida copia cada carácter una vez por cada grupo en el que se encuentra, 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, cada grupo tiene como máximo la mitad de longitud que el grupo que lo contiene, así que las copias se mantienen por debajo de 2m. Ningún enfoque puede superar O(m), porque la respuesta en sí tiene m caracteres.
¿Deberías resolver Decode String con recursión o con una pila?
Ambos hacen el mismo trabajo. La recursión sigue directamente el formato, ya que el cuerpo de un grupo es en sí una cadena codificada, y suele ser la opción más rápida de escribir en una entrevista. La versión con pila hace lo mismo en un solo bucle y mantiene los niveles externos sin terminar en una lista, por lo que un anidamiento muy profundo no puede desbordar la pila de llamadas. Si el entrevistador pregunta por una entrada anidada a miles de niveles de profundidad, la pila es la respuesta.
¿Cómo manejas cantidades 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. Restablece el contador a 0 en cuanto lo insertes, o se sumarán a él los dígitos del siguiente grupo.
¿Por qué la pila almacena el texto que venía antes de cada corchete?
Cuando se abre un [, el texto decodificado hasta ese momento en ese nivel aún no está terminado: las copias del grupo todavía deben ir después. Al apilarlo, lo mantienes a salvo mientras decodificas el cuerpo a partir de una cadena vacía. Cuando llega el ] correspondiente, desapilarlo te devuelve ese texto y le añades las copias.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def decodeString(s):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
s = "2[ab]3[c]x"
Esperado
"ababcccx"