Почему «5» .equals (5) не соответствует действительности? Разве они не оба они одинаковые, оба по 5?

Без предварительной обработки dict, O(n) - это лучшее, что вы можете сделать. Это не должно быть сложным:

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

(Не используйте dict и str в качестве имен переменных, это уже имена двух встроенных функции .)

Если вы можете препроизвести dict, подумайте о том, чтобы положить ключи в дерево префикса (aka trie ). Существует даже реализация Python в статье в Википедии.