Определение, существует ли префикс в наборе

Question

Учитывая набор строк, скажем:

"Alice"
"Bob"
"C"
"Ca"
"Car"
"Carol"
"Caroling"
"Carousel"

и, учитывая одну строку, скажем:

"Carolers"

Мне нужна функция, которая возвращает наименьший префикс, которого еще нет в массиве.

Для приведенного выше примера функция должна вернуть: «Caro». (Последующий вызов вернул бы «Кэрол»)

Я очень новичок в Ruby, и, хотя я, вероятно, мог бы взломать что-то некрасивое (используя мой мозг C / C ++ / Objective-C), я хотел бы научиться правильно (элегантно?) Кодировать это. *

Answer 1

В Ruby есть немного известный магический модуль, который называется Abbrev .

require 'abbrev'

abbreviations = Abbrev::abbrev([
  "Alice",
  "Bob",
  "C",
  "Ca",
  "Car",
  "Carol",
  "Caroling",
  "Carousel"
])
carolers = Abbrev::abbrev(%w[Carolers])
(carolers.keys - abbreviations.keys).sort.first # => "Caro"

Выше я взял первый элемент, но это показывает, что еще будет доступно.

pp (carolers.keys - abbreviations.keys).sort 
# >> ["Caro", "Carole", "Caroler", "Carolers"]

Оберните все вышеперечисленное в функцию, вычислите полученные недостающие элементы, а затем переберите их, передав их в блок, или используйте перечислитель, чтобы возвращать их один за другим.

Это то, что генерируется для одного слова. Для массива это сложнее.

require 'pp'
pp Abbrev::abbrev(['cat'])
# >> {"ca"=>"cat", "c"=>"cat", "cat"=>"cat"}

pp Abbrev::abbrev(['cat', 'car', 'cattle', 'carrier'])
# >> {"cattl"=>"cattle",
# >>  "catt"=>"cattle",
# >>  "cat"=>"cat",
# >>  "carrie"=>"carrier",
# >>  "carri"=>"carrier",
# >>  "carr"=>"carrier",
# >>  "car"=>"car",
# >>  "cattle"=>"cattle",
# >>  "carrier"=>"carrier"}

Answer 2

Ваш вопрос все еще не соответствует тому, что вы ожидаете в результате. Кажется, вам нужны префиксы, а не подстроки (так как "a" будет самой короткой подстрокой, которой еще нет в массиве) Для поиска префикса этого должно хватить:

array = [
"Alice",
"Bob",
"C",
"Ca",
"Car",
"Carol",
"Caroling",
"Carousel",
]

str = 'Carolers'

(0..str.length).map{|i|
  str[0..i]
}.find{|s| !array.member?(s)}

Answer 3

Очень простая версия (но не очень Rubyish):

str = 'Carolers'
ar = %w(Alice Bob C Ca Car Carol Caroling Carousel)

substr = str[0, n=1]
substr = str[0, n+=1] while ar.include? substr
puts substr

Answer 4

  => inn = ["Alice","Bob","C","Ca","Car","Carol","Caroling","Carousel"]
  => y = Array.new
  => str="Carolers"

Разбить заданную строку на массив

  => x=str.split('')
  # ["C","a","r","o","l","e","r","s"] 

Сформировать все комбинации

  => x.each_index {|i| y << x.take(i+1)}
  # [["c"], ["c", "a"], ["c", "a", "r"], ["c", "a", "r", "o"], ["c", "a", "r", "o", "l"], ["c", "a", "r", "o", "l", "e"], ["c", "a", "r", "o", "l", "e", "r"], ["c", "a", "r", "o", "l", "e", "r", "s"]]

Использование объединения для объединения

  => y =  y.map {|s| s.join }
  # ["c", "ca", "car", "caro", "carol", "carole", "caroler", "carolers"]

Выбратьпервый элемент из y, который недоступен во входном массиве

  => y.select {|item| !inn.include? item}.first

Вы получите "caro"

Соберите все

 def FindFirstMissingItem(srcArray,strtocheck)
   y=Array.new
   x=strtocheck.split('')
   x.each_index {|i| y << x.take(i+1)}
   y=y.map {|s| s.join}
   y.select {|item| !srcArray.include? item}.first
 end

и звоните

 => inn = ["Alice","Bob","C","Ca","Car","Carol","Caroling","Carousel"]
 => str="Carolers"

 FindFirstMissingItem inn,str

Answer 5

Я не совсем уверен, о чем вы просите, кроме примера кода на Ruby для поиска распространенных префиксов. Я предполагаю, что вы хотите найти наименьшую строку, которая является префиксом наибольшего количества строк в данном наборе. Вот пример реализации:

class PrefixFinder
  def initialize(words)
    @words = Hash[*words.map{|x|[x,x]}.flatten]
  end
  def next_prefix
    max=0; biggest=nil
    @words.keys.sort.each do |word|
      0.upto(word.size-1) do |len|
        substr=word[0..len]; regex=Regexp.new("^" + substr)
        next if @words[substr]
        count = @words.keys.find_all {|x| x=~regex}.size
        max, biggest = [count, substr] if count > max
        #puts "OK: s=#{substr}, biggest=#{biggest.inspect}"
      end
    end
    @words[biggest] = biggest if biggest
    biggest
  end
end

pf = PrefixFinder.new(%w(C Ca Car Carol Caroled Carolers))
pf.next_prefix # => "Caro"
pf.next_prefix # => "Carole"
pf.next_prefix # => "Caroler"
pf.next_prefix # => nil

Не комментируйте производительность (или правильность) этого кода, но он показывает некоторые идиомы Ruby (переменные экземпляра, итерация, хеширование и т. Д.).

Answer 6

Я не эксперт по Ruby, но я думаю, что вы, возможно, захотите решить эту проблему, превратив свой набор в три.После того, как вы построили дерево, ваша проблема может быть решена простым спуском от корня дерева, следуя всем краям букв в слове, пока вы не найдете узел, который не помечен как слово, или прогулкас три.В любом случае вы нашли узел, который не является частью какого-либо слова, и у вас есть самый короткий префикс вашего слова, которого нет в наборе.Более того, это позволит вам быстро выполнить любое количество проверок префиксов, так как после построения дерева алгоритм занимает самое большее время по длине строки.

Надеюсь, это поможет!