You would only need to do set(WORDS) once at the beginning of the program, so its amortized cost is low.
I wouldn't worry about the expense of set construction vs the expense of an n-squared algorithm.
caught me, I hadn't read through the article, wasn't sure whether or not WORDS was a set or a dict. Like desdiv points out, this isn't a big deal, you can maintain an equivalent WORDS structure that is a set.
Not quite. It'd have to be set(WORDS) instead of WORDS -- which'd be expensive. Or WORDS.keys(), which I'm not sure about -- I'd have to benchmark it.