<jupyter_start><jupyter_text>Jewels and StonesThis is [problem 771](https://leetcode.com/problems/jewels-and-stones/).**Input**: two strings _jewels_ and _stones_ (of lengths _j_ and _s_)\**Preconditions**: _jewels_ hasn't repeated characters; _j_, _s_ ≤ 50\**Output**: the number of characters from _stones_ that occur in _jewels_The following tests include the two examples in the problem statement.LeetCode uses 254 test cases.<jupyter_code>jewels50 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX'
stones50 = 'quite long and pointless text with maybe one jewel'
fox      = 'The quick brown fox jumped over the lazy dog'
tests = [
    # case          jewels          stones          output
    ('both empty',  '',             '',             0),
    ('some jewels', 'aA',           'aAAbbbb',      3), # example 1
    ('no jewels',   'z',            'ZZ',           0), # example 2
    ('many stones', 'qwertyuiop',   stones50,       24),
    ('both long',   jewels50,       fox,            36)
]

def test(function) -> None:
    for case in tests:
        inputs = case[1:-1]
        expected = case[-1]
        actual = function(*inputs)
        if actual != expected:
            print(case[0], 'FAILED:', actual, 'instead of', expected)

def time(function) -> str:
    result = %timeit -qo test(function)
    print(f'{result.best * 1e6:.3f}', 'µs')<jupyter_output><empty_output><jupyter_text>Version 1For each stone, check if it's a jewel.Complexity: O(_s_ · _j_) due to linear search of each stone in _jewels_.<jupyter_code>def v1(jewels: str, stones:str) -> int:
    counter = 0
    for stone in stones:
        if stone in jewels:
            counter += 1
    return counter

time(v1)<jupyter_output>5.412 µs<jupyter_text>The Pythonic one-line version uses the fact that Booleans are 0 and 1 in Python.<jupyter_code>def v1p(jewels: str, stones: str) -> int:
    return sum(stone in jewels for stone in stones)

time(v1p)<jupyter_output>8.451 µs<jupyter_text>Shorter code isn't necessarily faster. Version 2Put _jewels_ into a hash table to search it in constant time.Complexity: O(_j_) to construct hash table + O(_s_) to search.<jupyter_code>def v2(jewels: str, stones: str) -> int:
    jewels = set(jewels)
    counter = 0
    for stone in stones:
        if stone in jewels:
            counter += 1
    return counter

time(v2)<jupyter_output>6.529 µs<jupyter_text>The extra time to construct the set hasn't paid off.<jupyter_code>def v2p(jewels: str, stones: str) -> int:
    jewels = set(jewels)
    return sum(stone in jewels for stone in stones)

time(v2p)<jupyter_output>9.920 µs<jupyter_text>Version 3Invert the algorithm: go through *jewels*, count their occurrences in _stones_.Complexity: O(_j_ · _s_) due to linear search of each jewel in _stones_.In version 1 this was the worst-case complexity,while version 3 always does _j_ · _s_ steps.<jupyter_code>def v3(jewels: str, stones: str) -> int:
    counter = 0
    for jewel in jewels:
        counter += stones.count(jewel)
    return counter

time(v3)
def v3p(jewels: str, stones: str) -> int:
    return sum(stones.count(jewel) for jewel in jewels)

time(v3)<jupyter_output>10.831 µs<jupyter_text>Version 4Same as version 3, but put _stones_ in a bag (multiset) to only count them once.Complexity: O(_s_) to construct bag + O(_j_) if bag lookup takes constant time.<jupyter_code>from collections import Counter

def v4(jewels: str, stones: str) -> int:
    bag = Counter(stones)
    counter = 0
    for jewel in jewels:
        counter += bag[jewel]
    return counter

time(v4)<jupyter_output>19.640 µs<jupyter_text>I think `Counter` is implemented in Python and `set` in C,which could explain the run-time difference.<jupyter_code>def v4p(jewels: str, stones: str) -> int:
    bag = Counter(stones)
    return sum(bag[jewel] for jewel in jewels)

time(v4p)<jupyter_output>22.157 µs
{'fraction_non_alphanumeric': 0.10501810657009829, 'fraction_numerical': 0.02431453698913606, 'mean_word_length': 3.4602076124567476, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 36, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '309100', 'license': 'MIT', 'n_tokens_mistral': 1407, 'n_tokens_neox': 1310, 'n_words': 424, 'path': 'leetcode/jewels.ipynb', 'repo_name': 'mwermelinger/algorithmic-problems', 'size': '3866'}