fastest way to search python dict with partial keyword

Question

What is the fastest way to determine if a dict contains a key starting with a particular string? Can we do better than linear? How can we achieve an O(1) operation when we only know the start of a key?

Here is the current solution:

for key in dict.keys():
    if key.start_with(str):
        return True
return False

Answer 1

Without preprocessing the dict, O(n) is the best you can do. It doesn't have to be complicated, though:

any(key.startswith(mystr) for key in mydict)

(Don't use dict and str as variable names, those are already the names of two built-in functions.)

If you can preprocess the dict, consider putting the keys in a prefix tree (aka trie). There is even a Python implementation in the Wikipedia article.