regex - Crossword: split a string of letters into valid words from a dictionary

Question

Given:

1. A phrase with the spaces removed and converted to lower case - e.g. "ashotinthearm" from "a shot in the arm";
2. A dictionary which returns true or false if a word exists ("a", "as", "ash", "shot", "hot", etc., would all return true)

What is an efficient method to find the individual words which, when glued together with spaces, make up that phrase?

There may be more than one solution, even if some are gibberish:

• ashotinthearm (a shot in the arm, as hot in the arm)
• asintended (as intended, as in tended)
• brothersinlaw (brothers in law, brother sin law)
• guysanddolls (guys and dolls, guy sand dolls)
• haveascrewloose (have a screw loose, have as crew loose)
• ifeelthepinch (I feel the pinch, if eel the pinch)
• isinyourcourt (is in your court, I sin your court)
• manorhouse (manor house, man or house)
• manormouse (man or mouse, manor mouse)
• newzealand (New Zealand, new zeal and)
• oneatatime (one at a time, on eat a time)
• portableradio (portable radio, port able radio)
• scotspine (scots pine, scot spine)
• shopsoiled (shop soiled, shops oiled)

Would ideally prefer a PERL and/or regex solution, but grateful for any suggestions.

Answer 1

这个递归解决方案怎么样？

#!/usr/bin/perl -wW

use strict;

#global "constants"
my @words=("a", "as", "ash", "shot", "hot", "in", "the", "arm");
my %wordsHash = map { $_ => 1 } @words;

sub getParts($@);
sub dictionary($);

# returns true if in dict
sub dictionary($) {
    my ($str) = @_;
    return(defined($wordsHash{$str}));
}

# recursive function
sub getParts($@) {
    my ($phrase, @priorWords) = @_ ;
    print "DEBUG: step prior words(" . join(" ", @priorWords) . ") phrase($phrase) \n";

    #recursion end:
    if(!$phrase) {
        print "solution:" . join(" ", @priorWords) . "\n";
        return;
    }
    for my $i (1 .. length($phrase) ) {
        my $word = substr($phrase,0,$i);
        if(dictionary($word)) {
            getParts(substr($phrase,$i),(@priorWords,$word));
        }
    }
}

getParts("ashotinthearm", () );

输出是：

DEBUG: step prior words() phrase(ashotinthearm) 
DEBUG: step prior words(a) phrase(shotinthearm) 
DEBUG: step prior words(a shot) phrase(inthearm) 
DEBUG: step prior words(a shot in) phrase(thearm) 
DEBUG: step prior words(a shot in the) phrase(arm) 
DEBUG: step prior words(a shot in the a) phrase(rm) 
DEBUG: step prior words(a shot in the arm) phrase() 
solution:a shot in the arm
DEBUG: step prior words(as) phrase(hotinthearm) 
DEBUG: step prior words(as hot) phrase(inthearm) 
DEBUG: step prior words(as hot in) phrase(thearm) 
DEBUG: step prior words(as hot in the) phrase(arm) 
DEBUG: step prior words(as hot in the a) phrase(rm) 
DEBUG: step prior words(as hot in the arm) phrase() 
solution:as hot in the arm
DEBUG: step prior words(ash) phrase(otinthearm)