填字：從字典

Question

鑑於分裂的字母爲有效的字的字符串：

1. 與空間移出並轉換爲小寫的短語 - 例如「胳膊上的一槍」中的「ashotinthearm」;
2. 字典返回true，或者如果一個字存在虛假（ 「A」， 「因爲」， 「灰」， 「拍」， 「熱」，等等，都會返回true）

什麼是一種有效的方法來查找單詞，當與空間粘在一起時，就構成了這個詞組？

可以有多於一個的解決方案，即使有些是亂碼：

• ashotinthearm（在一針強心劑，在臂作爲熱）
• asintended（如預期，如在往往）
• brothersinlaw
• guysanddolls（紅男綠女，沙人玩偶）
• haveascrewloose（法律，哥哥罪依法兄弟）（有螺絲鬆動，有船員鬆）
• ifeelthepinch（我感到了壓力，如果鰻魚捏）
• isinyourcourt（是你的了，我的罪你的法院）
• 公館也許（莊園，人或房屋）
• manormouse（人或鼠標，莊園鼠標）
• 新西蘭（紐西蘭，新的熱情和）
• oneatatime（一次一個，在吃飯時間）
• portableradio（便攜式收音機，端口能夠收音機）
• scotspine（歐洲赤松， scot spine）
• shopsoiled（店弄髒，塗油店）

會非常喜歡PERL和/或正則表達式的解決方案，但感激的任何建議。

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)