Decode String
Uma string codificada representa texto repetido como k[text], que significa text escrito k vezes seguidas. Grupos podem ficar dentro de outros grupos, então 2[a3[b]] significa abbbabbb. Escreva uma função que receba uma string codificada s e retorne a string decodificada.
Letras fora de todos os colchetes permanecem como estão. Cada contagem é um número inteiro positivo escrito imediatamente antes de seu [, e os dígitos não aparecem em nenhum outro lugar.
Função
- sstring
- a string codificada
- Retornastring
- a string decodificada
Restrições
1 ≤ s.length ≤ 104scontém apenas letras minúsculas do inglês, dígitos,[e].sé uma codificação válida: cada[vem após uma contagem e tem um]correspondente, e nenhum colchete está vazio.- Toda contagem
ksatisfaz1 ≤ k ≤ 300e não tem zero à esquerda. - Os colchetes podem ser aninhados em até 100 níveis de profundidade.
- A string decodificada tem no máximo
5 × 104caracteres.
Exemplos
- Entrada
- s = "2[ab]3[c]x"
- Saída
- "ababcccx"
- Explicação
2[ab]geraababe3[c]geraccc. Oxfica fora de todos os colchetes, então é copiado como está, o que resulta emababcccx.
- Entrada
- s = "2[x3[yz]]"
- Saída
- "xyzyzyzxyzyzyz"
- Explicação
- Decodifique primeiro a parte interna:
3[yz]éyzyzyz, então o corpo do grupo externo éxyzyzyz. Escrito duas vezes, ficaxyzyzyzxyzyzyz.
- Entrada
- s = "q10[w]e"
- Saída
- "qwwwwwwwwwwe"
- Explicação
- A contagem é
10, lida a partir de dois dígitos, entãowaparece dez vezes entreqee. O código que lê apenas o dígito ao lado de[o repetiria 0 vezes.
+22 testes ocultos ao enviar
Para ir além
A string decodificada pode ser muito mais longa do que a entrada. Como você retornaria apenas o caractere na posição i da string decodificada, sem construí-la, quando o comprimento decodificado pode chegar a 10^18?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Você não pode escrever
3[...]até saber o que está dentro dos colchetes, e o conteúdo pode conter mais grupos. Que tipo de grupo você sempre consegue decodificar imediatamente?Um grupo sem nenhum grupo dentro dele pode ser expandido de uma só vez, então trabalhe de dentro para fora. Quando chega um
], o grupo que ele fecha está completo, e você precisa do texto e da contagem que estavam aguardando antes do[dele.Percorra a string uma vez, mantendo o texto construído até então e o número que está sendo lido. Ao encontrar
[, empilhe ambos e comece do zero. Ao encontrar], desempilhe-os e acrescente o texto atual, repetido, ao texto desempilhado. Construa cada número dígito por dígito para que10e300funcionem.
Solução
A contagem vem antes dos colchetes, mas você não pode escrever as cópias até saber o que há dentro deles, e o conteúdo pode conter mais grupos. Portanto, um grupo só pode ser expandido depois que todos os grupos dentro dele estiverem concluídos. Cada abordagem abaixo é uma maneira de concluir primeiro os grupos mais internos: reescrever a string de dentro para fora, deixar uma chamada recursiva concluir o grupo interno antes do externo ou manter os grupos externos inacabados em uma pilha. Abaixo, n é o comprimento da entrada, m é o comprimento da string decodificada e d é a profundidade máxima de aninhamento.
Expanda o grupo mais interno e, em seguida, repita
Intuição
Decodifique a string como você faria no papel. Encontre um grupo sem nenhum outro grupo dentro dele, escreva suas cópias no lugar e procure novamente. Em 2[x3[yz]], o grupo 3[yz] não tem nada dentro dele, então a string se torna 2[xyzyzyz], e mais uma expansão dá a resposta.
O primeiro ] da string sempre fecha um grupo desse tipo. Nenhum outro grupo foi fechado antes dele, então nada entre ele e seu [ pode ser um colchete. Esse [ é o mais próximo à sua esquerda, e a contagem é a sequência de dígitos imediatamente anterior a ele. Substitua a contagem, os colchetes e o conteúdo pelo conteúdo escrito k vezes e repita até não restar nenhum ].
Isso está correto, mas cada expansão reconstrói a string inteira. Com b grupos e uma string que cresce até cerca de m caracteres, são até b × m cópias de caracteres. O teste oculto com cerca de 1.300 grupos lado a lado custa cerca de 25 milhões de cópias para produzir 27.688 caracteres, quando bastaria uma passagem pela entrada.
Algoritmo
- Encontre o primeiro
]na string. Se não houver nenhum, a string está decodificada: retorne-a. - Vá para a esquerda a partir dele até o
[mais próximo. O texto entre eles é o corpo do grupo. - Continue indo para a esquerda, passando pelos dígitos antes desse
[, e leia-os como a contagemk. - Substitua tudo, do primeiro dígito até o
], pelo corpo escritokvezes. - Volte à etapa 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:]Descida recursiva
Intuição
O formato é recursivo: uma string codificada é uma sequência de letras e grupos, e o corpo de um grupo também é uma string codificada. Portanto, escreva uma função, decode, que leia a partir de uma posição compartilhada até encontrar o ] que encerra seu nível ou até chegar ao fim da entrada, e retorne o que leu, decodificado.
Quando decode encontra um dígito, ela lê o número inteiro, ignora o [ e chama a si mesma para decodificar o corpo. Essa chamada para no ] correspondente, porque qualquer ] mais interno já foi consumido por uma chamada mais profunda. A chamada que a invocou ignora o ], acrescenta o corpo k vezes e continua lendo. Para 2[x3[yz]], a chamada externa lê 2; a chamada seguinte lê x e 3; uma terceira chamada retorna yz; a chamada intermediária retorna xyzyzyz; e a chamada externa o escreve duas vezes.
Cada caractere da entrada é lido uma vez. O custo real está nas cópias: um caractere da saída é copiado uma vez para cada grupo que o envolve, então o tempo é O(n + m·d), para uma profundidade de aninhamento d. A recursão também chega a d chamadas de profundidade. Isso é aceitável para 100 níveis, mas uma entrada muito profunda pode estourar a pilha de chamadas: Python, por exemplo, para por padrão em 1.000 chamadas aninhadas.
Algoritmo
- Mantenha uma única posição
pos, compartilhada por todas as chamadas, começando no primeiro caractere. decode()faz um loop enquantoposestiver dentro da string e não estiver em um].- Ao encontrar uma letra, acrescente-a e avance.
- Ao encontrar um dígito, leia o número inteiro
k, pule o[, chamedecode()para o conteúdo, pule o]e acrescente o conteúdokvezes. - Retorne o que foi construído. A primeira chamada retorna a string 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()Uma passagem com uma pilha
Intuição
A recursão mantém um trecho de texto inacabado para cada grupo aberto, dentro dos seus quadros de chamada. Em vez disso, você pode manter esses trechos em uma pilha própria e ler a string em um único loop.
Acompanhe duas coisas no nível atual: current, o texto decodificado até agora, e count, o número que está sendo lido. Um dígito estende count como count × 10 + digit, para que 10 e 300 sejam calculados corretamente. Um [ abre um nível: empilhe current e count e, em seguida, reinicie ambos. Uma letra é acrescentada a current. Um ] fecha o nível: desempilhe o texto e a contagem salvos, e current passa a ser o texto salvo seguido de count cópias de current.
Rastreie 2[x3[yz]]. No primeiro [, você empilha (vazio, 2). O x faz com que current seja igual a x. No segundo [, você empilha (x, 3), e yz preenche um current novo. O primeiro ] desempilha (x, 3), então current passa a ser xyzyzyz. O último ] desempilha (vazio, 2), e current passa a ser xyzyzyzxyzyzyz.
Os grupos são fechados na ordem inversa àquela em que são abertos, então o topo da pilha é sempre o nível para o qual o ] retorna. O trabalho corresponde ao da recursão, O(n + m·d), mas o aninhamento profundo apenas aumenta uma lista, nunca a pilha de chamadas.
Algoritmo
- Comece com uma pilha vazia, um
currentvazio ecount = 0. - Ao encontrar um dígito, defina
count = count × 10 + digit. - Ao encontrar
[, empilhe o par (current,count) e, em seguida, redefinacurrentpara vazio ecountpara 0. - Ao encontrar uma letra, acrescente-a a
current. - Ao encontrar
], desempilhe (before,k) e definacurrentcomobeforeseguido dekcópias decurrent. - Após o último caractere, retorne
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)
Armadilhas e casos extremos
A maioria das respostas incorretas se deve à leitura da contagem ou a onde o texto salvo é colocado.
- Ler um único dígito como se fosse a contagem inteira. Em
q10[w]e, a contagem é 10. O código que pega apenas o dígito antes de[repetew0 vezes. - Esquecer de redefinir
countpara 0 depois de adicioná-lo à pilha. Os dígitos do próximo grupo são então somados ao número anterior, então2[a3[b]]interpreta a contagem interna como 23. - Colocar as cópias antes do texto salvo. Ao encontrar um
], o resultado é o texto antes do grupo seguido pelas cópias, entãoab2[c]éabcc, nãoccab. - Perder letras no nível superior. O
xem2[ab]3[c]xestá fora de todos os colchetes e ainda faz parte da resposta. - Acrescentar um caractere de cada vez a uma string longa e imutável. Cada acréscimo pode copiar a string inteira, o que transforma uma resposta de 50,000 caracteres em bilhões de cópias. Reúna as partes em uma lista ou em um construtor de strings.
Perguntas frequentes4
Qual é a complexidade de tempo de Decode String?
A leitura da entrada é O(n). A construção da saída copia cada caractere uma vez para cada grupo em que ele está, então o total é O(n + m·d), em que m é o comprimento decodificado e d é a profundidade de aninhamento. Quando todas as contagens são pelo menos 2, cada grupo tem no máximo metade do comprimento do grupo que o contém, então o total de cópias fica abaixo de 2m. Nenhuma abordagem pode superar O(m), porque a própria resposta tem m caracteres.
Você deve resolver Decode String com recursão ou com uma pilha?
Ambas fazem o mesmo trabalho. A recursão segue diretamente o formato, já que o corpo de um grupo é, por si só, uma string codificada, e geralmente é a opção mais rápida de escrever em uma entrevista. A versão com pilha faz a mesma coisa em um único loop e mantém os níveis externos inacabados em uma lista, então um aninhamento muito profundo não pode estourar a pilha de chamadas. Se o entrevistador perguntar sobre uma entrada aninhada milhares de níveis, a pilha é a resposta.
Como você lida com contagens com mais de um dígito?
Monte o número à medida que o lê: comece em 0 e, para cada dígito, defina count = count × 10 + digit. Quando chegar o [, o número estará completo, então 300[a] resulta em 300. Redefina a contagem para 0 assim que adicioná-la, ou os dígitos do próximo grupo serão somados a ela.
Por que a pilha armazena o texto que veio antes de cada colchete?
Quando um [ abre, o texto decodificado até então nesse nível ainda não está completo: as cópias do grupo ainda precisam vir depois dele. Colocá-lo na pilha o mantém seguro enquanto você decodifica o corpo a partir de uma string vazia. Quando o ] correspondente chega, removê-lo da pilha devolve esse texto, e você acrescenta as cópias a ele.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def decodeString(s):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
s = "2[ab]3[c]x"
Esperado
"ababcccx"