Assuming that the dictionary is arbitrary as well, just comparing the string to the strings in the dictionary (or hashing it) it takes O(n), regardless of the data-structure you use.
Is that relevant to real-world use? You mention Python in TFA - I'm no expert but I believe it does string interning, and caches the results of string hashes, which would suggest real-world performance should be constant over time in both cases.