数组 – 高效的方式(在Ruby中),确定数组/字符串中最大的匹配序列

发布时间：2020-12-17 03:43:11 所属栏目：百科来源：网络整理

导读：让我们说我有两个单词阵列： array1 = ["hello","world","i","am","in","the","world"]array2 = ["This","is","hello","message"] 哪个,可以很容易地由两个字符串表示： string1 = "hello world i am in the world"string2 = "This is the hello world messa

让我们说我有两个单词阵列：

array1 = ["hello","world","i","am","in","the","world"]
array2 = ["This","is","hello","message"]

哪个,可以很容易地由两个字符串表示：

string1 = "hello world i am in the world"
string2 = "This is the hello world message"

让我们假设我现在正在使用数组.

我想找到array2中最大的子数组,它在array1中以相同的顺序出现.

所以,如果你打算以可以想象的最慢的方式去做,比方说,你会说：

>从array2中获取所有6个字的子数组(其中有一个).

>它是按顺序出现在array1中的吗？没有

>从array2中获取所有5个字的子数组(其中有两个).

>按顺序,它们中的任何一个出现在array1中吗？没有

>从array2获取所有4字的子数组.

>它们中的任何一个按顺序出现在array1中吗？没有

等等,直到我们到达
>从array2获取所有2个字的子数组.

>它们中的任何一个按顺序出现在array1中吗？是的：[“你好”,“世界”].停.

但是,这感觉效率很低.有人能看到更好的方法吗？我正在使用Ruby,但我对一般算法以及如何使用该特定语言感兴趣.

请注意,这不仅仅是数组交集,因为(至少在ruby中)并不关心元素的顺序,我关心它.

谢谢！

解决方法

这是一个快速工作的解决方案,将比较仅减少到数组中常见的元素：

array1 = ["hello","message"]

common_words = array1 & array2

stringified_array1 = array1.join(' ')
stringified_array2 = array2.join(' ')

(common_words.length - 1).downto(0).map do |n|
  stringified_combo = array1[0..n].join(' ')

  if stringified_array1.include?(stringified_combo) && stringified_array2.include?(stringified_combo)
    stringified_combo.split($,)
  end 
end.compact.max

这样就可以得到两个数组之间的共同点,并从最大到最小测试它们.你在第一个数组中检查它们是否有序,然后在第二个数组中它们是否存在.

我相信这样做很有效,但很高兴收到任何意见和反馈,

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!