Does a set work like a dictionary without values?

Question

This question is the python version of: Is there a Collection that works like a Dictionary without the values?

I want a data structure that has a list of english words in it, but not their definitions.

Basically: given a sequence of letters, I want to be able to do constant-time O(1) lookup to determine if that sequence is in the english dictionary.

Would a set() or frozenset() be the correct choice?

I know that I could use a dictionary where each key's value is None, but that seems like a waste of memory space.

Answer 1

Yes, set is the right tool for this job. You can find out whether a word is in the set with in, which operates in O(1) time. Adding words is done with the add member which takes amortized O(1) time. It additionally has all the usual finite-set operations: union, intersection, difference, etc.:

>>> A = set(["foo", "bar", "baz"])
>>> B = set(["foo", "ham", "spam"])
>>> "foo" in A
True
>>> "bar" in B
False
>>> A | B
set(['bar', 'ham', 'spam', 'foo', 'baz'])
>>> A & B
set(['foo'])
>>> A - B
set(['bar', 'baz'])
>>> B - A
set(['ham', 'spam'])