Leetcode 14: Longest common prefix problem

leetcode_14_longest_common_prefix.rb

Leetcode 14: Longest common prefix problem

# @param {String[]} strs
# @return {String}
# def longest_common_prefix(strs)
#   smallest = strs.min {|x,y| x.length <=> y.length}
#   #smallest = strs[0]
#   has_to_cmp = {}
#   smallest.split("").each_with_index {|char_x, ind| has_to_cmp["#{char_x}"] ? has_to_cmp["#{char_x}"] << ind : has_to_cmp["#{char_x}"] = [ind]}
#   # will generate {'f': [0], 'l': [1], ...}
#   min = smallest.length
#   strs.each do |str_c|
#       return "" if min == 0
#       loc_min = 0
#       str_c.split("").each_with_index do |curr_chr, curr_i|
#           break if has_to_cmp["#{curr_chr}"] == nil || !has_to_cmp["#{curr_chr}"].include?(curr_i)
#           loc_min += 1
#       end
#       min = [min, loc_min].min
#   end
#   return smallest.split("")[0...min].join('')
# end

# Another solution, sort array : sort by characters, so [abc, brg, abx].sort will give
# [abc abx brg] now only need to check first and last elements

class String
  def common_prefix(other)
    length = [self.length, other.length].min
    prefix = ''
    length.times do |i|
      break if self[i] != other[i]
      prefix += self[i]
    end
    prefix
  end
end

def longest_common_prefix(strs)
    strs = strs.sort
    strs[0].common_prefix(strs[-1])
end