Как Вы записали бы программу для нахождения самой короткой панграммы в списке слов?

Это вариант задачи укрытия набора (также известная как проблема набора ):

В качестве входных данных вам предоставляется несколько наборов. У них могут быть некоторые общие элементы. Вы должны выбрать минимальное количество этих наборов, чтобы выбранные вами наборы содержали все элементы, которые содержатся в любом из наборов во входных данных. В 1972 году [...] было показано, что он является NP-полным [,], а оптимизационная версия покрытия множества NP-трудна.

Это вариант, потому что мы ищем минимальное количество букв, а не минимальное количество слов. Но я думаю, что это все еще NP-сложно, а это означает, что вы не сможете добиться большего, чем грубая сила.

Вот алгоритм O (n) для другой проблемы, когда у вас есть строка вместо списка слов. как вход. . Это был мой надзор, но я оставлю решение здесь, потому что не хочу его удалять :)

Поскольку нас интересуют только персонажи, это значительно упрощает задачу. Сохраните сопоставление каждого символа [a-z] с его положением в строке. Одной этой карты достаточно, чтобы определить, есть ли у нас панграмма и какова ее длина.

1. Initialize a map of all alphabets to null
2. Initialize shortest_pangram to { length: ∞, value: undefined }
3. Loop through each "character" in given string
  3.1 Update the value of map[character] to current string index
  3.2 If we have a pangram, and its the shortest so far, record its length/value
4. shortest_pangram should have our result

Созданной нами карты достаточно, чтобы определить, есть ли у нас панграмма - если все значения на нашей карте не равны нулю, у нас есть панграмма.

Чтобы найти длину текущей панграммы, вычтите максимальное значение из минимального значения на нашей карте. Помните, что перед тем, как найти длину, мы должны проверить, является ли это панграммой.

Вот наивная неоптимизированная реализация в Ruby:

class Pangram
  def initialize(string)
    @input = string.downcase.split('')
    @map = {}
    ('a'..'z').each { |c| @map[c] = nil }
    infinity = 1.0/0.0
    @best = { :length => infinity, :string => nil }
  end

  def shortest
    @input.each_with_index do |c, index|
      @map[c] = index if @map.key?(c)
      if pangram? and length < @best[:length]
        @best[:length] = length
        @best[:string] = value
      end
    end
    @best
  end

  def pangram?
    @map.values.all? { |value| !value.nil? }
  end

  def length
    @map.values.max - @map.values.min
  end

  def value
    @input[@map.values.min..@map.values.max].join('')
  end
end

Для использования создайте экземпляр класса и передайте ему всю строку. Вызовите .shortest, чтобы найти длину самой короткой панграммы и соответствующей подстроки.

pangram = Pangram.new("..")
print pangram.shortest