Jewels and Stones

Bierz kamienie po jednym. Dla każdego kamienia przejdź przez jewels i zatrzymaj się przy pierwszej literze, która jest mu równa. Dopasowanie dodaje 1 do licznika. W pierwszym przykładzie kamień u jest porównywany z r i R, niczego nie znajduje i niczego nie dodaje.

Możesz zatrzymać się przy pierwszym dopasowaniu, ponieważ litery oznaczające rodzaje klejnotów są różne, więc kamień może pasować najwyżej do jednego z nich. Kamień, który nie jest klejnotem, trzeba porównać z każdą literą oznaczającą klejnot, zanim się o tym przekonasz.

Przy j rodzajach klejnotów i s kamieniach potrzeba do j × s porównań. Tutaj j ≤ 52, więc nawet 10^4 kamieni wymaga około 5 × 10^5 porównań, a skanowanie kończy się na czas. Nieefektywność staje się widoczna, gdy lista rodzajów się powiększa: to samo wyszukiwanie jest powtarzane dla każdego kamienia.

Odpowiedź na pytanie „czy ta litera jest klejnotem?” jest taka sama za każdym razem, gdy zadasz je dla tej samej litery. Odpowiedz więc na nie raz dla każdego rodzaju: utwórz zbiór z liter w jewels. Zbiór sprawdza przynależność w stałym czasie, więc sprawdzenie każdego kamienia wymaga jednego wyszukania zamiast skanowania.

W pierwszym przykładzie zbiór to {r, R}. Podczas przechodzenia po rubyRRr wyniki wyszukiwania to: tak, nie, nie, nie, tak, tak, tak — cztery klejnoty. Utworzenie zbioru wymaga j kroków, a przejście po literach — s, więc łączna złożoność to O(j + s).

Zbiór zawiera najwyżej 52 litery. W języku bez wbudowanego zbioru to samo zadanie można wykonać za pomocą tablicy flag indeksowanej kodem znaku.