2
\$\begingroup\$

I've written a phrase-matching method to return the longest matching phrase from two Strings in Ruby. My method looks like this and works as expected:

class String
  def phrase_in_common(other)
    n = [size, other.size].min
    while n > 0 do
      other_words = other.downcase.split.each_cons(n)
      string_words = split.each_cons(n)
      matching_words = string_words.find { |cons_words| other_words.include?(cons_words.map(&:downcase)) }
      return matching_words&.join(' ') if matching_words
      n -= 1
    end
  end
end

>> string = "Hello world, please come to my house next week"
>> other = "Hello friends, please come to my party next week"
>> string.phrase_in_common(other)
=> "please come to my"

My question is, can (and should) this be accomplished in a more Ruby way, perhaps by replacing the while with an Enumerable method of some kind?

To clarify, the phrase-matching should be based on words, so for example:

>> "this phrase".phrase_in_common("his phrase")
=> "phrase"

Also, note that the method is case-insensitive in matching and uses the case of the subject String for the return value:

>> "Greatest Show On The Earth".phrase_in_common("Silliest Show on the Earth")
=> "Show On The Earth"
\$\endgroup\$
  • \$\begingroup\$ Are you looking for the longest substring, or things minus non \w characters? \$\endgroup\$ – tadman Sep 14 '17 at 17:24
  • \$\begingroup\$ Looking to match the longest substring, but I wouldn't want to pick up, for example, the comma before the matching string. So I wouldn't want my example to return ", please come to my" \$\endgroup\$ – moveson Sep 14 '17 at 17:26
  • \$\begingroup\$ Spec is here if that's helpful. \$\endgroup\$ – moveson Sep 14 '17 at 17:44
  • \$\begingroup\$ Those preserve case, though. \$\endgroup\$ – tadman Sep 14 '17 at 17:46
  • \$\begingroup\$ Right--I want to match case-insensitive but preserve the case of the phrase that's returned, based on the subject String. Please see the last example I added to the question. \$\endgroup\$ – moveson Sep 14 '17 at 17:49
1
\$\begingroup\$

It seems that you are trying to get the longest common subsequence. There are several implementation of this algorithm and you can find an example on Rosetta Code.

A working recursive implementation implementation could be:

# Split your sentence into words and manipulate the content. E.g.
# - downcase all chars
# - split by some chars such as space, punctuation and so on

def split_into_words(string)
  string.downcase.split(/[\s\.,;\'\"]/)
end

def longest_subsequence(xstr, ystr)
  return '' if xstr.empty? || ystr.empty?

  x, *xs = xstr
  y, *ys = ystr

  if x == y
    x + " " + longest_subsequence(xs, ys)
  else
    [longest_subsequence(xstr, ys), longest_subsequence(xs, ystr)].max_by {|x| x.size}
  end
end

def phrase_in_common(string1, string2)
  xstr = split_into_words(string1)
  ystr = split_into_words(string2)
  longest_subsequence(xstr, ystr).strip
end

This would pass all your specs, but it returns '' instead of nil when the longest substring is empty.

You can slightly change this implementation to include int inside class String eventually

Edit 2017-10-04

As remarked by moveson, in Rails we can easily make this method to return nil instead of an empty string:

def phrase_in_common(string1, string2)
  xstr = split_into_words(string1)
  ystr = split_into_words(string2)
  longest_subsequence(xstr, ystr).strip.presence
end
\$\endgroup\$
  • \$\begingroup\$ I'm using Rails, so the last part is easily remedied by adding .presence after .strip. \$\endgroup\$ – moveson Oct 3 '17 at 23:57
  • \$\begingroup\$ I think it also needs .squeeze(' ') after the .strip. Otherwise it sometimes returns phrases with more than one space between words. \$\endgroup\$ – moveson Oct 4 '17 at 0:05
  • \$\begingroup\$ I haven't use squeeze it may have some side effects \$\endgroup\$ – mabe02 Oct 4 '17 at 10:16
  • \$\begingroup\$ About the .presence after .strip and I will edit my answer accordingly \$\endgroup\$ – mabe02 Oct 4 '17 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.