DPの繰り返しの関係は？

Question

有効な単語を含む辞書があるとします。

すべてのスペースが削除された入力文字列が与えられた場合、その文字列が有効な単語で構成されているかどうかを判断します。

辞書は、O（1）ルックアップを提供するハッシュテーブルであると仮定できます。

これについては繰り返してください。私は本の中でこの質問を見つけましたが、この本は無回答です。

Answer 1

IsWordValid(S) = for word in dict: 
        if S.startsWith(word) and IsWordValid(S[word.length:]) 
          return true 
       return false 
IsWordValid(null) = true 

Answer 2

ここはMathematicaのコードです。私は最近のコードゴルフのために開発を始めました。
これは最小限の一致、非貪欲な、再帰アルゴリズムです。それが文（スペースなし）「ペンは剣よりもmighterですが、」返すことを意味:)

findAll[s_] := 
    Module[{a = s, b = "", c, sy = "="}, 
    While[ 
    StringLength[a] != 0, 
    j = ""; 
    While[(c = findFirst[a]) == {} && StringLength[a] != 0, 
    j = j <> StringTake[a, 1]; 
    sy = "~"; 
    a = StringDrop[a, 1]; 
    ]; 
    b = b <> " " <> j ; 
    If[c != {}, 
    b = b <> " " <> c[[1]]; 
    a = StringDrop[a, StringLength[c[[1]]]]; 
    ]; 
    ]; 
    Return[{StringTrim[StringReplace[b, " " -> " "]], sy}]; 
] 

findFirst[s_] := 
    If[s != "" && (c = DictionaryLookup[s]) == {}, 
    findFirst[StringDrop[s, -1]], Return[c]]; 

サンプル入力

ss = {"twodreamstop", 
     "onebackstop", 
     "butterfingers", 
     "dependentrelationship", 
     "payperiodmatchcode", 
     "labordistributioncodedesc", 
     "benefitcalcrulecodedesc", 
     "psaddresstype", 
     "ageconrolnoticeperiod", 
     "month05", 
     "as_benefits", 
     "fname"} 

出力{ "ペンは剣よりもかもしれない小胞体である}

twodreamstop    = two dreams top 
onebackstop    = one backstop 
butterfingers    = butterfingers 
dependentrelationship  = dependent relationship 
payperiodmatchcode  = pay period match code 
labordistributioncodedesc ~ labor distribution coded es c 
benefitcalcrulecodedesc ~ benefit c a lc rule coded es c 
psaddresstype    ~ p sad dress type 
ageconrolnoticeperiod  ~ age con rol notice period 
month05     ~ month 05 
as_benefits    ~ as _ benefits 
fname      ~ f name 

HTH