letters.rb

require 'rspec/autorun'

def letters(a, b)
  indexes = b.each_char.map do |letter|
    a.each_char.each_with_index.select {|l, _| l == letter }.map {|_, i| i }
  end

  start = indexes.shift

  if indexes.empty?
    [start]
  else
    start.product(*indexes).select {|x| x == x.sort }
  end
end

describe "letters" do
  let(:a) { "hello world" }

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2,3,9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should ==  [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end

Brute force is better than nothing ;)

I'll keep trying with my iterative/recursive version, which prunes dead ends as it goes.

This is a solution with recursion.

require 'rspec/autorun'

##
# find letter combinations recursively
def letters(text, pattern)
  start = 0
  result = find_all_from_pattern(text, start, pattern)
end

def find_all_from_pattern(text, from, pattern)
  letter = pattern[0]
  remainder = pattern[1..-1]
  r = find_all_from_letter(text, from, letter)
  if remainder.size > 0
    r.each_with_object([]) do |previous, results|
      one_deeper = find_all_from_pattern(text, (previous+1), remainder)
      one_deeper.each do |deeper|
        results  << ([previous] + deeper)
      end
    end
  else # leaf node, end of iteration
    r
  end.map{ |e| Array(e) }
end

def find_all_from_letter(text, from, letter)
  [].tap do |result|
    while(match = find_one_from_letter(text, from, letter))
      result << match
      from = match + 1
    end
  end
end

def find_one_from_letter(text, from, letter)
  return nil unless letter
  index = text[from..-1].index(letter)
  index && (index + from)
end

describe "letters" do
  let(:a) { "hello world" }

  specify "example 0" do
    letters(a, "z").should == []
  end

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2], [3], [9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end

describe "find_all_from_letter" do
  let(:text) { "hello world" }

  it "finds h from 0" do
    find_all_from_letter(text, 0, 'h').should == [0]
  end

  it "finds e from 0" do
    find_all_from_letter(text, 0, 'e').should == [1]
  end

  it "finds all l from 0" do
    find_all_from_letter(text, 0, 'l').should == [2, 3, 9]
  end

  it "finds e from 1" do
    find_all_from_letter(text, 1, 'e').should == [1]
  end

  it "finds all l from 1" do
    find_all_from_letter(text, 1, 'l').should == [2, 3, 9]
  end

  it "returns nil for h from 1" do
    find_all_from_letter(text, 1, 'h').should  == []
  end

  it "returns not the first l (on 2) from 3" do
    find_all_from_letter(text, 3, 'l').should == [3, 9]
  end
end

describe "find_one_from_letter" do
  let(:text) { "hello world" }

  it "returns nil when letter is nil" do
    find_one_from_letter(text, 0, nil).should be_nil
  end

  it "finds h from 0" do
    find_one_from_letter(text, 0, 'h').should == 0
  end

  it "finds e from 0" do
    find_one_from_letter(text, 0, 'e').should == 1
  end

  it "finds first l from 0" do
    find_one_from_letter(text, 0, 'l').should == 2
  end

  it "finds e from 1" do
    find_one_from_letter(text, 1, 'e').should == 1
  end

  it "finds first l from 1" do
    find_one_from_letter(text, 1, 'l').should == 2
  end

  it "returns nil for h from 1" do
    find_one_from_letter(text, 1, 'h').should be_nil
  end

  it "returns second l (on 3) from 3" do
    find_one_from_letter(text, 3, 'l').should == 3
  end
end

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

Here is my attempt, it was meant to be iterative. With some more effort the recursion could probably be unwound. This might be logically identical to one of the other solutions. https://gist.github.com/jlsync/7162908

def get_results(string, s_i, chars, c_i )
  finds = []
  while i = string.index(chars[c_i], s_i)
    if chars[c_i + 1]
      if more_finds = get_results(string, i + 1, chars , c_i + 1)
        finds += more_finds.map{|a| a.unshift(i)}
      else
        return nil
      end
    else
      finds << [i]
    end
    s_i = i + 1
  end
  return finds
end

def letters(a, b)
  return get_results(a, 0, b.split(//), 0 )
end

This one runs pretty fast (2+ times faster than the next fastest on haystacks > 100 chars and needles > 4 chars, and increasingly much better as the strings get larger).

def letters(haystack_str, needle_str)
  haystack = haystack_str.chars
  needle   = needle_str.chars

  @pos_cache   = haystack.each.with_index.with_object(Hash.new { |h, k| h[k] = [] }) { |(c, i), h| h[c] << i if needle.include?(c) }
  @match_cache = Hash.new { |h, k| h[k] = {} }
  matches(needle)
end

def matches(chars, current_pos = -1)
  return [[]] unless chars.any?

  char, *rest = *chars
  @match_cache[char][current_pos] ||= begin
    this_matches = @pos_cache[char].select { |candidate_pos| candidate_pos > current_pos }
    this_matches.each_with_object([]) do |this_pos, memo|
      matches(rest, this_pos).each do |rest_matches|
        memo << [this_pos, *rest_matches]
      end
    end
  end
end

Benchmarks here: https://gist.github.com/02fd396e56ca8a8d2efe

Wanted to try my luck, and it turned out very similar to other solutions. It was lots of fun, thanks! :-)

module Refines
  refine Array do
    def strictly_increasing?
      each_cons(2).all? {|x, y| x < y }
    end
  end

  refine String do
    def char_indexes
      each_char
        .with_index
        .with_object(Hash.new { |h, k| h[k] = [] }) { |(char, idx), hsh|
          hsh[char] << idx
        }
    end
  end
end

using Refines

def letter_match(target, str)
  first_set, *rest = target.char_indexes.values_at(*str.split(//))

  first_set.product(*rest).select { |arr| arr.strictly_increasing? }
end

Specs used:

describe "LetterMatch" do
  let(:a) { "hello world" }

  specify "single match" do
    expect(letter_match(a, "e")).to eq [[1]]
  end

  specify "single letter with multiple matches" do
    expect(letter_match(a, "l")).to eq [[2],[3],[9]]
  end

  specify "multiple matches, example 1" do
    expect(letter_match(a, "el")).to eq [[1,2], [1,3], [1,9]]
  end

  specify "multiple matches, example 2" do
    expect(letter_match(a, "lo")).to eq [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "multiple matches, example 3" do
    expect(letter_match(a, "lod")).to eq [[2,4,10], [2,7,10], [3,4,10], [3,7,10]]
  end
end