Jewels and Stones

Q: Qual é a complexidade de tempo de Jewels and Stones?

Com um conjunto, é O(j + s) : j etapas para criar o conjunto a partir de jewels e uma consulta em tempo constante para cada uma das s pedras. Percorrer jewels para cada pedra é O(j × s) .

Q: Você consegue resolver sem um conjunto?

Sim. As letras são letras inglesas, então um array de 128 ou 256 sinalizadores indexados pelo código do caractere funciona como um conjunto sem precisar de hashing. Marque cada letra de joia e, em seguida, conte as pedras cujo sinalizador está definido. O stones.count(jewels) do Ruby faz todo o trabalho em uma única chamada, mas o array de sinalizadores mostra o que acontece por baixo dos panos.

InicianteHashing

+10

Você recebe duas strings de letras. Cada letra em jewels representa um tipo de joia, e nenhuma letra se repete. Cada letra em stones representa uma pedra que você possui. Retorne quantas das suas pedras são joias. As letras diferenciam maiúsculas de minúsculas: "a" e "A" são tipos diferentes.

Função

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

jewelsstring: os tipos de pedras que contam como joias, uma letra para cada
stonesstring: as pedras que você possui, uma letra para cada
Retornainteger: o número de pedras cuja letra aparece nas joias

Restrições

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Ambas as strings contêm apenas letras do alfabeto inglês, minúsculas e maiúsculas.
As letras de jewels são todas diferentes.

Exemplos

Entrada: jewels = "rR"stones = "rubyRRr"
Saída: 4
Explicação: Os tipos de joias são r e R. Em rubyRRr, as pedras r, R, R e r correspondem, enquanto u, b e y não correspondem, então a resposta é 4.

Entrada: jewels = "z"stones = "ZZZ"
Saída: 0
Explicação: O único tipo de joia é a letra minúscula z. Todas as pedras são letras maiúsculas Z, um tipo diferente, então nenhuma delas conta.

+12 testes ocultos ao enviar

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Para cada pedra, você precisa de uma resposta: esta letra é uma joia? Procurar cada pedra na string jewels repete a mesma busca várias vezes. Coloque as letras das joias em um conjunto uma vez, e cada pedra se torna uma única consulta.

Examine as joias em busca de cada pedra

Intuição

Pegue as pedras uma de cada vez. Para cada pedra, percorra jewels e pare na primeira letra igual a ela. Uma correspondência acrescenta 1 à contagem. No primeiro exemplo, a pedra u é comparada com r e R, não encontra nada e não acrescenta nada.

Você pode parar na primeira correspondência porque as letras das joias são todas diferentes, então uma pedra pode corresponder a, no máximo, uma delas. Uma pedra que não é uma joia precisa ser comparada com todas as letras das joias antes que você saiba.

Com j tipos de joias e s pedras, são até j × s comparações. Aqui, j ≤ 52, então até mesmo 10^4 pedras exigem cerca de 5 × 10^5 comparações, e a busca termina a tempo. O desperdício fica evidente quando a lista de tipos aumenta: a mesma busca é repetida para cada pedra.

Algoritmo

Defina count como 0.
Para cada pedra, compare-a com cada letra de jewels.
Ao encontrar a primeira letra igual, adicione 1 a count e passe para a próxima pedra.
Retorne 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

Coloque as joias em um conjunto

Intuição

A pergunta "esta letra é uma joia?" tem sempre a mesma resposta quando você a faz sobre a mesma letra. Então responda uma vez por tipo: construa um conjunto a partir das letras de jewels. Um conjunto verifica a pertinência em tempo constante, então cada pedra custa uma consulta em vez de uma varredura.

No primeiro exemplo, o conjunto é {r, R}. Percorrendo rubyRRr, as consultas dizem sim, não, não, não, sim, sim, sim: quatro joias. Construir o conjunto leva j passos e percorrer a sequência leva s, então o total é O(j + s).

O conjunto contém no máximo 52 letras. Em uma linguagem sem um conjunto integrado, um array de sinalizadores indexado pelo código do caractere faz o mesmo trabalho.

Algoritmo

Crie um conjunto contendo cada letra de jewels.
Defina count como 0.
Para cada pedra, adicione 1 a count se o conjunto a contiver.
Retorne count.

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

Armadilhas e casos extremos

O algoritmo é um único loop. As respostas erradas vêm da forma como as letras são comparadas e contadas.

Ignorar maiúsculas e minúsculas. Converter ambas as strings para minúsculas faz com que z corresponda a Z, e o segundo exemplo retorna 3 em vez de 0.
Contar os tipos distintos de joias em vez das pedras. rubyRRr contém dois tipos de joia, mas quatro pedras preciosas; cada pedra conta, inclusive as repetidas.
Criar o conjunto dentro do loop das pedras. Recriá-lo para cada pedra custa j passos a cada vez e traz de volta o O(j × s) da varredura. Crie-o uma vez, antes do loop.
Trocar os argumentos. O conjunto deve conter jewels, e o loop deve percorrer stones. Com os papéis invertidos, o segundo exemplo conta o único tipo de joia z em relação às pedras e ainda retorna 0, mas ("a", "aaa") retorna 1 em vez de 3.

Perguntas frequentes3

Qual é a complexidade de tempo de Jewels and Stones?

Com um conjunto, é O(j + s): j etapas para criar o conjunto a partir de jewels e uma consulta em tempo constante para cada uma das s pedras. Percorrer jewels para cada pedra é O(j × s).

Por que usar um conjunto hash para Jewels and Stones?

Cada pedra faz o mesmo tipo de pergunta: se sua letra é uma joia. Um conjunto hash responde a isso em tempo constante, enquanto pesquisar na string jewels leva um tempo proporcional ao seu comprimento. Você paga uma vez para criar o conjunto e economiza em cada pedra a partir daí.

Você consegue resolver sem um conjunto?

Sim. As letras são letras inglesas, então um array de 128 ou 256 sinalizadores indexados pelo código do caractere funciona como um conjunto sem precisar de hashing. Marque cada letra de joia e, em seguida, conte as pedras cujo sinalizador está definido. O stones.count(jewels) do Ruby faz todo o trabalho em uma única chamada, mas o array de sinalizadores mostra o que acontece por baixo dos panos.

Python

def numJewelsInStones(jewels, stones):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

jewels = "rR"
stones = "rubyRRr"

Esperado