Отношение повторения для DP? - PullRequest
Новая
       41

Отношение повторения для DP?

0 голосов
/ 06 апреля 2011

Предположим, у вас есть словарь, который содержит допустимые слова.

Если для входной строки удалены все пробелы, определите, состоит ли строка из допустимых слов.

Можно предположить, чтословарь является хеш-таблицей, которая обеспечивает поиск O (1).

Пожалуйста, дайте рекуррентное отношение для этого.Я нашел этот вопрос в книге, но книга не дает ответа?

Ответы [ 2 ]

2 голосов
/ 06 апреля 2011 
IsWordValid(S) = for word in dict:
                    if S.startsWith(word) and IsWordValid(S[word.length:])
                          return true
                 return false
IsWordValid(null) = true
0 голосов
/ 06 апреля 2011

Вот код в Mathematica, который я начал разрабатывать для недавнего кода в гольф.
Это минимальный подход, не жадный, рекурсивный алгоритм. Это означает, что предложение «ручка сильнее меча» (без пробелов) возвращает {«ручка может быть лучше меча}:) 

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

НТН

...