How to find the longest shared prefix among all words in a string with Ruby

1 Answer

0 votes
#
# Normalize a string:
# - Convert letters to lowercase
# - Replace any non-letter with a space
#
def normalize(text)
  text.chars.map { |ch| ch.match?(/[A-Za-z]/) ? ch.downcase : " " }.join
end

#
# Extract words from a string.
#
def extract_words(text)
  normalize(text).split(/\s+/)
end

#
# Compute the common prefix between two strings.
#
def common_prefix(a, b)
  limit = [a.length, b.length].min
  idx = 0
  idx += 1 while idx < limit && a[idx] == b[idx]
  a[0...idx]
end

#
# Find the longest shared prefix among ANY subset of words.
#
def longest_shared_prefix(text)
  words = extract_words(text)
  return ["", 0, 0, []] if words.empty?

  best_prefix = ""
  best_group  = []

  # Compare every pair of words
  words.combination(2).each do |w1, w2|
    prefix = common_prefix(w1, w2)
    next if prefix.empty?

    # Find all words sharing this prefix
    group = words.select { |w| w.start_with?(prefix) }

    # Update best result
    if prefix.length > best_prefix.length
      best_prefix = prefix
      best_group  = group
    end
  end

  [best_prefix, best_prefix.length, best_group.length, best_group]
end

#
# Main execution
#
s = "The Lowly inhabitants of the lowland were surprised to see the lower branches of the trees."

prefix, prefix_len, group_count, group_words = longest_shared_prefix(s)

puts "Longest shared prefix:"
puts "#{prefix} | prefix_len=#{prefix_len} | group_count=#{group_count} | #{group_words.inspect}"

  
  
=begin
run:

Longest shared prefix:
lowl | prefix_len=4 | group_count=2 | ["lowly", "lowland"]

=end

 



answered Sep 12 by avibootz

Related questions

...