Re:Retiring a Great Interview Problem
by kragen on Monday August 08, 2011 @07:01PM
(#2861909)
There's a library for constructing a deterministic regular expression from a dictionary, by the way, which would right away give you the exponential-time result. If you wrapped it in a * and applied it with a guaranteed-linear-time regular-expression engine like RE2, you'd find out whether the string was segmentable (and as a bonus you wouldn't have to construct the deterministic RE yourself) but I don't know if you'd get the actual segments.
[ Parent
| on HN ]
There are no comments on this comment yet.