算法全部构造在 Ruby

Question

我被困在这个算法中，输出不是我所期望的，目标是将数组内部的所有可能方式检索到 2D 数组中，连接可能的多个解决方案以重新创建给定的目标。

预期输出

[
["purp", "le"]
["p","ur", "p", "le"]
]

OutPut []

def all_contruct(target, wordBank)
  return [[]] if target == ''
  result = []

  wordBank.each do |word|
    if target.index(word) == 0
      suffix = target.slice(word.length)

    suffixResult = all_contruct(suffix, wordBank)
    suffixWay  = suffixResult.map { |e| [ word, *e]  }

    result.push(*suffixWay)
    end
  end
  return result
end



all_contruct("purple",["purp","p","ur","le","purpl"])
#=> []

Answer 1

方法如下：

def all_contruct target, wordBank
  possibleWords = wordBank.select{|word| target.start_with? word}
  possibleWords.each_with_object([]) do |word,result|
    rest = target.delete_prefix word
    if rest.empty?
      result << [word]
    else
      send(__method__,rest,wordBank).each {|tail| result << [word] + tail}
    end
  end
end

all_contruct("purple",["purp","p","ur","le","purpl"])
#=> [["purp", "le"], ["p", "ur", "p", "le"]]

更新:没想到，竟然是单行本

def all_contruct target, wordBank
  wordBank.select{|w| target.start_with? w}.each_with_object([]) { |w,r| (t = target.delete_prefix w).empty? ? r << [w] : send(__method__,t,wordBank).each {|c| r << [w] + c} }
end

算法全部构造在 Ruby

Algorithms All construct in Ruby

ruby

algorithm

recursion

2d