Jewels and Stones

Q: ¿Cuál es la complejidad temporal de Jewels and Stones?

Con un conjunto es O(j + s) : j pasos para crear el conjunto a partir de jewels y una búsqueda en tiempo constante por cada una de las s piedras. Recorrer jewels por cada piedra es O(j × s) .

Q: ¿Puedes resolverlo sin un conjunto?

Sí. Las letras son letras inglesas, así que una matriz de 128 o 256 indicadores indexados por código de carácter funciona como un conjunto sin necesidad de hash. Marca cada letra de joya y luego cuenta las piedras cuyo indicador está activado. stones.count(jewels) de Ruby hace todo el trabajo en una sola llamada, pero la matriz de indicadores muestra lo que ocurre por debajo.

PrincipianteHashing

+10

Recibes dos cadenas de letras. Cada letra de jewels representa un tipo de joya, y ninguna letra se repite. Cada letra de stones representa una piedra que tienes. Devuelve cuántas de tus piedras son joyas. Se distingue entre mayúsculas y minúsculas: "a" y "A" son tipos diferentes.

Función

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: los tipos de piedras que cuentan como joyas, una letra cada uno
stonesstring: las piedras que tienes, una letra cada una
Devuelveinteger: el número de piedras cuya letra aparece en las joyas

Restricciones

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Ambas cadenas contienen solo letras inglesas, minúsculas y mayúsculas.
Las letras de jewels son todas diferentes.

Ejemplos

Entrada: jewels = "rR"stones = "rubyRRr"
Salida: 4
Explicación: Los tipos de gema son r y R. En rubyRRr, las piedras r, R, R y r coinciden, mientras que u, b e y no, así que la respuesta es 4.

Entrada: jewels = "z"stones = "ZZZ"
Salida: 0
Explicación: El único tipo de joya está en minúscula: z. Todas las piedras son Z mayúsculas, de un tipo diferente, así que ninguna cuenta.

+12 pruebas ocultas al enviar

Pistas

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

0 de 3 abiertas

Solución

Para cada piedra necesitas una respuesta: ¿es esta letra una joya? Buscar en la cadena jewels cada piedra repite el mismo recorrido una y otra vez. Coloca las letras de las joyas en un conjunto una sola vez, y cada piedra se convierte en una única búsqueda.

Escanea las joyas en busca de cada piedra

Intuición

Toma las piedras una a una. Para cada piedra, recorre jewels y detente en la primera letra que coincida con ella. Una coincidencia suma 1 al conteo. En el primer ejemplo, la piedra u se compara con r y R, no encuentra ninguna coincidencia y no suma nada.

Puedes detenerte en la primera coincidencia porque todas las letras de las joyas son diferentes, así que una piedra puede coincidir como máximo con una de ellas. Una piedra que no es una joya debe compararse con todas las letras de las joyas antes de que puedas saberlo.

Con j tipos de joyas y s piedras, se realizan hasta j × s comparaciones. Aquí j ≤ 52, así que incluso 10^4 piedras requieren unas 5 × 10^5 comparaciones y el recorrido termina a tiempo. El desperdicio se nota cuando aumenta la lista de tipos: se vuelve a realizar la misma búsqueda para cada piedra.

Algoritmo

Establece count en 0.
Para cada piedra, compárala con cada letra de jewels.
Cuando encuentres la primera letra igual, suma 1 a count y pasa a la siguiente piedra.
Devuelve count.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Pon las joyas en un conjunto

Intuición

La pregunta «¿esta letra es una joya?» siempre tiene la misma respuesta cada vez que la haces sobre la misma letra. Así que respóndela una vez por tipo: crea un conjunto a partir de las letras de jewels. Un conjunto responde si un elemento pertenece a él en tiempo constante, así que cada piedra cuesta una consulta en lugar de un recorrido.

Para el primer ejemplo, el conjunto es {r, R}. Al recorrer rubyRRr, las consultas dicen sí, no, no, no, sí, sí, sí: cuatro joyas. Crear el conjunto lleva j pasos y el recorrido lleva s, así que el total es O(j + s).

El conjunto contiene como máximo 52 letras. En un lenguaje sin un conjunto integrado, un arreglo de indicadores indexado por el código del carácter hace el mismo trabajo.

Algoritmo

Construye un conjunto que contenga cada letra de jewels.
Establece count en 0.
Por cada piedra, suma 1 a count si el conjunto la contiene.
Devuelve count.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

Errores comunes y casos límite

El algoritmo es un solo bucle. Las respuestas incorrectas se deben a cómo se comparan y cuentan las letras.

Ignorar las mayúsculas y minúsculas. Pasar ambas cadenas a minúsculas hace que z coincida con Z, y el segundo ejemplo devuelve 3 en lugar de 0.
Contar los tipos de joyas distintos en vez de las piedras. rubyRRr contiene dos tipos de joyas, pero cuatro piedras preciosas; cuenta cada piedra, incluidas las repetidas.
Crear el conjunto dentro del bucle de piedras. Volver a crearlo para cada piedra cuesta j pasos cada vez y recupera la complejidad O(j × s) del recorrido. Créalo una vez, antes del bucle.
Intercambiar los argumentos. El conjunto debe contener jewels y el bucle debe recorrer stones. Con los roles invertidos, el segundo ejemplo compara el único tipo de joya, z, con las piedras y aun así obtiene 0, pero ("a", "aaa") devuelve 1 en lugar de 3.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Jewels and Stones?

Con un conjunto es O(j + s): j pasos para crear el conjunto a partir de jewels y una búsqueda en tiempo constante por cada una de las s piedras. Recorrer jewels por cada piedra es O(j × s).

¿Por qué usar un conjunto hash para Jewels and Stones?

Cada piedra plantea el mismo tipo de pregunta: si su letra es una joya. Un conjunto hash responde en tiempo constante, mientras que buscar en la cadena jewels lleva un tiempo proporcional a su longitud. Pagas una vez para crear el conjunto y ahorras con cada piedra a partir de entonces.

¿Puedes resolverlo sin un conjunto?

Sí. Las letras son letras inglesas, así que una matriz de 128 o 256 indicadores indexados por código de carácter funciona como un conjunto sin necesidad de hash. Marca cada letra de joya y luego cuenta las piedras cuyo indicador está activado. stones.count(jewels) de Ruby hace todo el trabajo en una sola llamada, pero la matriz de indicadores muestra lo que ocurre por debajo.

Python

def numJewelsInStones(jewels, stones):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

jewels = "rR"
stones = "rubyRRr"

Esperado