letters.rb

require 'rspec/autorun'
 
module DominicRecursion
  def self.letters(haystack, needles, index = 0)
    # base case: if the letters to match are empty, we've succeeded
    return [[]] if needles.empty?

    # base case: if the word to match in is empty, we've failed
    return [] if haystack.empty?

    result = []

    if needles[0] == haystack[0]
      tail = letters(haystack[1..-1], needles[1..-1], index + 1)
      result += tail.map { |t| [index] + t }
    end

    result + letters(haystack[1..-1], needles, index + 1)
  end
end

module DominicLists
  def self.letters(haystack, needles)
    indices = Hash[haystack.each_char.with_index.group_by { |(char, _)| char }.map { |(char, values)| [char, values.map { |(_, index)| index }] }]

    results = indices[needles[0]].map { |i| [i] }
    needles[1..-1].each_char do |char|
      results = results.flat_map do |r|
        indices[char].drop_while { |i| i < r.last }.map { |i| r + [i] }
      end
    end

    results
  end
end
 
[DominicRecursion, DominicLists].each do |c|
  describe "#{c.name}: letters" do
    let(:a) { "hello world" }
   
    specify "example 1" do
      c.letters(a, "e").should == [[1]]
    end
   
    specify "example 2" do
      c.letters(a, "l").should == [[2],[3],[9]]
    end
   
    specify "example 3" do
      c.letters(a, "el").should == [[1,2], [1,3], [1,9]]
    end
   
    specify "example 4" do
      c.letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
    end
   
    specify "example 5" do
      c.letters(a, "lod").should ==  [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
    end
  end
end

Using the benchmarking code from https://gist.github.com/textgoeshere/02fd396e56ca8a8d2efe

Desktop$ ruby letters-benchmarking.rb
Running each test once. Test will take about 2 minutes.
DominicLists is similar to Dave
Dave is faster than Jason by 2x ± 1.0
Jason is similar to Peter
Peter is faster than DominicRecursion by 4x ± 1.0
DominicRecursion is similar to Tom
Tom is faster than Roland by 3x ± 1.0
Roland is faster than DominicOriginal by 2x ± 1.0