ruby - 如何编写一个函数，通过共享字母将每个前一个单词与下一个单词连接起来

Question

返回结果字符串(删除重叠中的重复字符)以及所有字符串对中共享字母的最小数量。示例

join(["oven", "envier", "erase", "serious"]) ➞ ["ovenvieraserious", 2]
join(["move", "over", "very"]) ➞ ["movery", 3]
join(["to", "ops", "psy", "syllable"]) ➞ ["topsyllable", 1]

# "to" and "ops" share "o" (1)
# "ops" and "psy" share "ps" (2)
# "psy" and "syllable" share "sy" (2)
# the minimum overlap is 1

join(["aaa", "bbb", "ccc", "ddd"]) ➞ ["aaabbbcccddd", 0]笔记更具体地说，查看前一个单词的结尾字母和下一个单词的开头字母之间的重叠。

Answer 1

代码

def doit(arr)
  a, nbr = arr.each_cons(2).map do |s1,s2|
    n = [s1.size, s2.size].min.downto(1).find { |n| s1[-n..-1] == s2[0,n] }
    n.nil? ? [s2, 0] : [s2[n..-1],n]
  end.transpose
  [a.unshift(arr.first).join, nbr.min]
end

示例

doit ["oven", "envier", "erase", "serious"]
    #=> ["ovenvieraserious", 2] 
doit ["move", "over", "very"]
    # ["movery", 3]
doit ["to", "ops", "psy", "syllable"]
    #["topsyllable", 1]

说明

步骤如下。

arr = ["oven", "envier", "erase", "serious"]

e = arr.each_cons(2)
  #=> #<Enumerator: ["oven", "envier", "erase", "serious"]:each_cons(2)>

参见Enumerable#each_cons 。我们可以看到该枚举器将生成​​并通过将其转换为数组传递给 map 的元素。

e.to_a
  #=> [["oven", "envier"], ["envier", "erase"], ["erase", "serious"]]

继续，

b = e.map do |s1,s2|
  n = [s1.size, s2.size].min.downto(1).find {|n| s1[-n..-1] == s2[0,n]}
  n.nil? ? [s2, 0] : [s2[n..-1],n]
end
  #=> [["vier", 2], ["ase", 2], ["rious", 2]]
a, nbr = b.transpose
  #=> [["vier", "ase", "rious"], [2, 2, 2]] 
a #=> ["vier", "ase", "rious"] 
nbr
  #=> [2, 2, 2]

从 b.transpose 计算 a 和 nbr 利用 Array Decomposition 。继续，

c = a.unshift(arr.first)
  #=> ["oven", "vier", "ase", "rious"] 
d = c.join
  #=> "ovenvieraserious" 
e = nbr.min
  #=> 2 
[d, e]
  #=> ["ovenvieraserious", 2] 

现在考虑b的计算。第一个元素由 e 生成并传递给 map，后者将其传递给其 block ，并将值分配给 block 变量(同样，借助数组分解)。

s1, s2 = e.next
  #=> ["oven", "envier"]
s1
  #=> "oven"
s2
  #=> "envied"

现在执行 block 计算。

f = [s1.size, s2.size].min
  #=> [4,6].min
  #=> 4
g = f.downto(1).find { |n| s1[-n..-1] == s2[0,n] }
  #=> 2

在计算g时， block 计算按如下方式进行。

 n = 4
 s1[-n..-1] == s2[0,n]
   #=> "oven" == "envi" => false

 n = 3
 s1[-n..-1] == s2[0,n]
   #=> "ven" == "env" => false

 n = 2
 s1[-n..-1] == s2[0,n]
   #=> "en" == "en" => true

这意味着，当n #=> 2时，由s1的最后n个字符组成的字符串等于第一个 s2 的 >n 个字符，这是具有该属性的 n 的最大值。

然后

 n.nil? ? [s2, 0] : [s2[n..-1],n]
   #=> [s2[n..-1],n]
   #=> ["envied"[2..-1],2]
   #=> ["vied",2]

然后生成 e 的下一个值，传递给 map 并为 block 变量分配新值:

s1, s2 = e.next
  #=> ["oven", "envier"]

然后进行区 block 计算，依此类推。