Variantes de mayúsculas y minúsculas
La misión
Problema
Un string (cadena) mezcla letras y dígitos. Cada letra puede escribirse en minúscula o en mayúscula, mientras que los dígitos nunca cambian. Devuelve todos los strings que puedes producir de esta forma. Ordénalos de modo que, para cada letra de izquierda a derecha, la opción en minúscula vaya antes que la de mayúscula.
Ejemplos
Input: s = "a1b"
Output: ["a1b", "a1B", "A1b", "A1B"]
Por qué: dos letras, dos opciones cada una, cuatro strings
Input: s = "3Z"
Output: ["3z", "3Z"]
Por qué: no importa si la letra venía en mayúscula o minúscula: se listan ambas formas
Input: s = "42"
Output: ["42"]
Por qué: caso límite: sin letras hay exactamente un string, la propia entrada
Pistas
0 / 3
Recorre el string posición por posición y pregúntate cuántas opciones tiene realmente cada una. Los dígitos y las letras responden de forma distinta.
Es un árbol de decisión en el que las letras se dividen en dos ramas y los dígitos pasan de largo. El número de hojas es 2 elevado al número de letras.
Llama recursivamente sobre la posición. En una letra, escribe su minúscula en un buffer compartido y llama recursivamente; luego sobrescríbela con la mayúscula y vuelve a llamar. En un dígito, solo llama recursivamente. Cuando la posición llegue al final, guarda el buffer unido.
- Tiempo objetivo
- O(n · 2^L)
- Espacio objetivo
- O(n · 2^L)
Restricciones
- the string holds only letters and digits
Solución
Cada letra es una decisión del tipo incluir o excluir con exactamente dos ramas, y cada dígito es un nivel con una sola rama, así que la profundidad de recursión es la longitud del string y las hojas son las respuestas. Un único buffer guarda el string actual; cada rama sobrescribe su propia posición antes de bajar, y por eso no hace falta un paso explícito para deshacer. Probar primero la minúscula da el orden pedido. Con L letras en un string de longitud n hay 2 elevado a L resultados de longitud n, así que el tiempo es O(n por 2 elevado a L) y la profundidad de recursión es 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']¿Lo que te frena es la idea y no el código? Subconjuntos lo explica.