trie

data-structure

implementation

trie = {}
for w in words:
    root = trie
    for c in w:
        if c not in root:
            root[c] = {}
        root = root[c]
        matched = root.get('$') > 0
    matched = root.get('$') > 0
    root['$'] = root.get('$', 0) + 1

python trick for short implementation

trie = (T := lambda: defaultdict(T))()
for w in words:
    root = trie
    for c in w:
        root = root[c]
        matched = root.get('$') > 0
    matched = root.get('$') > 0
    root['$'] = root.get('$', 0) + 1