Geek Answers Handbook

How would you write a program to find the shortest pangram in a list of words?

Given a word list that contains the letters az at least once, how would you write a program to find the shortest pangram counted by the number of characters (not including spaces) as a combination of words?

Since I'm not sure if short answers exist, this is not code golf, but just a discussion of how you approach it. However, if you think you can write a short program that will do this, then go ahead, and this may turn into a golf code :)

+5
source share
4 answers

, , NP-, NP- , .

. Set Cover , , . , Set Cover, N , M. , , N * M , , . ( a, b, c... x, y, z, ), , pangram , G.

, NP-, , , NP- , (, ) . Set-Cover , , ( Set-Cover , ).

, NP- , - . .

+6

(aka ):

. . , , . [...], NP- 1972 [,], NP-hard.

, , . , NP-hard, , , .

+2

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

, , - , .

pangram, min . , , .

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 = Pangram.new("..")
print pangram.shortest
+1

, , , , . , , ( ). , , :

, . , , A * . github.

, , :

. , "BAD" "DAB" "ABD". , , ~ 250 000 ~ 31 000 , .

, NP , . :

, , #vowels/#unusedLetters. - , , .

, , . , , . ( , )

3-

. , , 3- , . , , ABC , ABCD [ABC, ABD, BCD]. , .

So, in the end, I need the meaning of the commonality of letters to be with me, I have a dictionary showing all 26, select 3 possible sets of letters, compared with the number of times these combos appear on my word. Then I use this to prefer search nodes, where the rest of the letters have more valid 3-letter combos.

+1
source

More articles:


All Articles