查找字符串数组中的公共字符串(ruby)

Question

鉴于我有一个包含3个字符串的数组:

["Extra tv in bedroom",
 "Extra tv in living room",
 "Extra tv outside the shop"]

如何找到所有字符串共有的最长字符串？

Answer 1

这是一种红宝石的做法.如果你有很多字符串或者它们很长,你应该使用更高级的算法:

def longest_common_substr(strings)
  shortest = strings.min_by &:length
  maxlen = shortest.length
  maxlen.downto(0) do |len|
    0.upto(maxlen - len) do |start|
      substr = shortest[start,len]
      return substr if strings.all?{|str| str.include? substr }
    end
  end
end

puts longest_common_substr(["Extra tv in bedroom",
                            "Extra tv in living room",
                            "Extra tv outside the shop"])