Finding common string in array of strings (ruby)

Question

Given I have an array of 3 strings:

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

How do I find the longest string all strings have in common?

Answer 1

Here's a rubyish way of doing it. You should use a more advanced algorithm if you have a bunch of strings or they are very long, though:

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"])

Answer 2

If you want to search for the beginning of all strings:

Source

def substr( a )
    return "" unless (a.length > 0)
    result = 0
    (0 ... a.first.length).each do |k|
        all_matched = true
        character = a.first[k]
        a.each{ |str| all_matched &= (character == str[k]) }
        break unless all_matched
        result+=1
    end
    a.first.slice(0,result)
end

Test

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

puts substr( input ) + "."

Output

Extra tv .