I am convinced that matching parens and finding a word that is the reverse are equivalent problems. (With the word finding possibly even more difficult, because each character could act as opening as well as closing brace).

As we aparently both know, the regular expressions (as defined by computer science) can't verify an arbitrary set of parens. You need a grammar for that.

However, Perl regular expressions are more powerfull than the conventional CS definition of RE, and they can match an arbitrary length string of parens.

Take a look at Regexp::Common::balanced . I didn't look at the code, but from the docs it appears to be what you need.

Now all you need to do is change the regexp so that it will work with different kinds of parens (instead of just one opening and one closing), append each candidate word to the pattern word, and see if the match returns true. Piece of cake :-)

Except that you transformed a O(n) search into an O(n^2) search. Which is not a good thing, unless you get a percentage from hardware sales :-)