[LRUG] Recursion diversion

Tom Stuart tom at codon.com
Fri Oct 25 12:39:41 PDT 2013


On 25 Oct 2013, at 14:21, Andrew Stewart wrote:
> Given two strings a and b, I would like to find all the occasions where the letters of b appear in the same order in a.  The result should be an array of arrays where each inner array contains the indices of b's matches in a.

Here's a terse-but-cute recursive version, which searches breadth-first rather than using brute force:

def letters(a, b, starting_at = 0)
  if b.empty?
    [[]]
  else
    a.each_char.with_index.drop(starting_at).
      select { |c, _| c == b[0] }.map(&:last).
      flat_map { |i| letters(a, b[1..-1], i.succ).map(&[i].method(:+)) }
  end
end

Cheers,
-Tom


More information about the Chat mailing list