3

我有一个原句

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
4

2 回答 2

1 
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 点......

于 2012-07-02T22:52:12.937 回答
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)

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

于 2012-07-02T23:32:06.547 回答