I did this using a trie a few years back. It wasn't rocket surgery and I believe it was tons faster than the regex solution (and it scored multiple solutions in order to more often avoid the common pitfalls already discussed). But Clinton paid me for it (and I'd have to find it on backup) so I'll wait for his permission before posting it.

But it also wouldn't be a lot of work to do over. See Re: find all paths of length n in a graph (Boggle solver) for an example of making and using a trie for a somewhat similar purpose.