Variações de maiúsculas e minúsculas
A missão
Problema
Uma string mistura letras e dígitos. Cada letra pode ser escrita em minúscula ou em maiúscula, enquanto os dígitos nunca mudam. Retorne todas as strings que você consegue produzir dessa forma. Liste-as de modo que, para cada letra da esquerda para a direita, a opção minúscula venha antes da maiúscula.
Exemplos
Input: s = "a1b"
Output: ["a1b", "a1B", "A1b", "A1B"]
Por quê: duas letras, duas escolhas cada, quatro strings
Input: s = "3Z"
Output: ["3z", "3Z"]
Por quê: não importa como a letra estava escrita, as duas formas são listadas
Input: s = "42"
Output: ["42"]
Por quê: edge case: sem letras, há exatamente uma string, a própria entrada
Dicas
0 / 3
Percorra a string uma posição por vez e pergunte-se quantas opções cada posição realmente tem. Dígitos e letras respondem a essa pergunta de formas diferentes.
Esta é uma árvore de decisão em que as letras se dividem em dois ramos e os dígitos passam direto. O número de folhas é dois elevado ao número de letras.
Faça a recursão sobre a posição. Numa letra, escreva a forma minúscula num buffer compartilhado e chame recursivamente; depois, sobrescreva com a forma maiúscula e chame de novo. Num dígito, apenas chame recursivamente. Quando a posição chegar ao fim, junte o buffer e registre o resultado.
- Tempo-alvo
- O(n · 2^L)
- Espaço-alvo
- O(n · 2^L)
Restrições
- the string holds only letters and digits
Solução
Cada letra é uma decisão no estilo incluir ou excluir, com exatamente dois ramos, e cada dígito é um nível com um único ramo; assim, a profundidade da recursão é o tamanho da string e as folhas são as respostas. Um único buffer guarda a string atual; cada ramo sobrescreve a própria posição antes de descer, e é por isso que nenhum passo explícito de desfazer é necessário. Tentar a forma minúscula primeiro dá a ordem exigida. Com L letras numa string de tamanho n, há 2 elevado a L resultados de tamanho n, então o tempo é O(n vezes 2 elevado a L) e a profundidade da recursão é O(n).
def case_variants(s):
out, path = [], list(s)
def build(i):
if i == len(s): # every position is decided
out.append("".join(path))
return
if s[i].isalpha():
for ch in (s[i].lower(), s[i].upper()): # two branches
path[i] = ch # overwriting doubles as the undo
build(i + 1)
else:
build(i + 1) # a digit has a single branch
build(0)
return out
print(case_variants("a1b")) # -> ['a1b', 'a1B', 'A1b', 'A1B']
print(case_variants("3Z")) # -> ['3z', '3Z']
print(case_variants("42")) # -> ['42']Travou na ideia, e não no código? Subconjuntos explica isso.