从较小的短语重建原始句子

Question

我有一个原句

sent = "For 15 years photographer Kari Greer has been documenting wildfires and the men and women who battle them."

和短语：

phrases = [
  "For 15 years",
  "wildfires and the men and women who battle them",
  "has been documenting wildfires",
  "been documenting wildfires and the men and women who battle them",
  "documenting wildfires and the men and women who battle them",
  "them",
  "and the men and women who battle them",
  "battle them",
  "wildfires",
  "the men and women",
  "the men and women who battle them",
  "15 years",
  "photographer Kari Greer"
]

我想从短语中重建原始句子（不丢失任何单词）并将选定的短语存储在新数组中，保持顺序，以便我得到：

 result = [
   "For 15 years",
   "photographer Kari Greer",
   "has been documenting wildfires",
   "and the men and women who battle them"
]

编辑：重要的是result具有最少数量的元素。

编辑：以下是适用于更复杂情况的答案代码版本：

 sent ="Shes got six teeth Pink says of her 13-month-old daughter but shes not a biter"      
 phrases = ["her 13-month-old daughter", "she", "says of her 13-month-old daughter", "a biter", "got six teeth", "Pink", "of her 13-month-old daughter", "s not a biter", "She", "six teeth", "s got six teeth", "Shes got six"] 
def shortest(string, phrases)
 string = string.gsub(/.|n|'|,|?|!|:|;|'|"|`|n|,|?|!/, '')
 best_result = nil
 phrases.each do |phrase|
  if string.match(/#{phrase}/)
    result = [phrase] + shortest(string.sub(/#{phrase}/, "").strip, phrases)
        best_result = result  if (best_result.nil? || result.size < best_result.size) # && string == result.join(" ")
      end
    end
  best_result || []
end

Answer 1

def shortest(string, phrases)
  best_result = nil
  phrases.each do |phrase|
    if string.match(/A#{phrase}/)
      result = [phrase] + shortest(string.sub(/A#{phrase}/, "").strip, phrases)
      best_result = result if (best_result.nil? || result.size < best_result.size) && string.match(Regexp.new("\A#{result.join("\s?")}\Z"))
    end
  end
  best_result || []
end
result = shortest(sent.gsub(/./, ""), phrases)

编辑：更新了算法，允许某些短语之间没有空格。

Answer 2

def solve arr
    len = arr.count
    (len - 1).downto(0) do |i|
        phrase = arr[0..i].join(" ")
        if $phrases.include?(phrase)
            return [phrase] if len - 1 == i
            ans = solve arr[(i + 1)..(len - 1)]
            return [phrase] + [ans] if ans.count != 0
        end
    end
    []
end
words = sent.gsub(".", "").split(" ")
res = solve words
puts res.flatten.inspect

我认为这应该有效。它查找匹配的最大短语，并检查短语的其余部分是否可以分解为短语。

可能有更好的方法可以做到这一点，但它是凌晨 4 点在这里......