Ruby 字谜拼图-解网

问：

我是 Ruby 中的乞丐，我需要有关如何让程序返回包含“入口”的列表的说明

问题：给定一个单词和一个可能的字谜列表，选择正确的子列表。

给定“listen”和候选列表，如“enlists”、“google”、“inlets”、“banana”，程序应该返回一个包含“inlets”的列表。

这就是我能够做到的

puts 'Enter word'
word_input = gets.chomp
puts 'Enter anagram_list'
potential_anagrams = gets.chomp
potential_anagrams.each do |anagram|
end

假设我的word_input是，这就是程序应该如何运行，但我不知道如何让它工作。"hello"

is_anagram? word: 'hello', anagrams: ['helo', 'elloh', 'heelo', 'llohe']
# => 'correct anagrams are: elloh, llohe'

真的很感激想法。

Ruby 方法 Anagram

def anagrams(list, word)
  ltr_freq = word.each_char.tally
  puts "ltr_freq = #{ltr_freq}"
  list.select do |w|
    puts "\nw = '#{w}'"
    if w.size != word.size
      puts "words differ in length"
      false
    else
      puts "w.each_char.tally = #{w.each_char.tally}"
      if w.each_char.tally == ltr_freq
        puts "character frequencies are the same"
        true
      else
        puts "character frequencies differ"
        false
      end
    end
  end
end

anagrams(list, 'hello')
ltr_freq = {"h"=>1, "e"=>1, "l"=>2, "o"=>1}

w = 'helo'
words differ in length

w = 'elloh'
w.each_char.tally = {"e"=>1, "l"=>2, "o"=>1, "h"=>1}
character frequencies are the same

w = 'heelo'
w.each_char.tally = {"h"=>1, "e"=>2, "l"=>1, "o"=>1}
character frequencies differ

w = 'llohe'
w.each_char.tally = {"l"=>2, "o"=>1, "h"=>1, "e"=>1}
character frequencies are the same
  #=>["elloh", "llohe"]

可能的改进

表达式的潜在弱点

w.each_char.tally == ltr_freq

就是在得出结论之前必须确定单词中所有唯一字母的频率，即使例如，单词中的第一个字母没有出现在单词中。我们可以采取以下补救措施。wwword

def anagrams(list, word)
  ltr_freq = word.each_char.tally
  list.select do |w|
    next false unless w.size == word.size
    ltr_freqs_match?(w, ltr_freq.dup)
  end
end

def ltr_freqs_match?(w, ltr_freq)
  w.each_char do |c|
    return false unless ltr_freq.key?(c)
    ltr_freq[c] -= 1
    ltr_freq.delete(c) if ltr_freq[c].zero?
  end
  true
end

人们必须根据上述原始版本测试此变体，以确定哪个版本最快。这种变体的优点是，一旦发现单词中给定字符的累积计数大于相同字母的总数，它就会终止（短路）比较。同时，它是用 C 语言编写的，所以它可能仍然更快。anagramswwordtally

1赞 pjs 12/15/2022 #3

我采取了创建一个类来追求可重用性的策略。对于一次性用法来说，这是矫枉过正的，但允许您建立一组已知单词，然后根据需要多次轮询它以获取多个候选单词的字谜。

此解决方案基于哈希和集合构建，使用单词的排序字符作为共享相同字母的一组单词的索引。散列是 O（1），集合是 O（1），如果我们将单词视为具有有界长度，则键的计算也是 O（1），从而产生每个单词的恒定时间的整体复杂度。

我已经注释了代码，但如果有任何不清楚的地方，请随时询问。

require 'set'

class AnagramChecker
  def initialize
    # A hash whose default value is an empty set object
    @known_words = Hash.new { |h, k| h[k] = Set.new }
  end

  # Create a key value from a string by breaking it into individual
  # characters, sorting, and rejoining, so all strings which are
  # anagrams of each other will have the same key.
  def key(word)
    word.chars.sort.join
  end

  # Add individual words to the class by generating their key value
  # and adding the word to the set. Using a set guarantees no
  # duplicates of the words, since set contents are unique.
  def add_word(word)
    word_key = key(word)
    @known_words[word_key] << word
    # return the word's key to avoid duplicate work in find_anagrams
    word_key
  end

  def find_anagrams(word)
    word_key = add_word(word)     # add the target word to the known_words
    @known_words[word_key].to_a   # return all anagramatic words as an array
  end

  def inspect
    p @known_words
  end
end

生成已知单词库如下所示：

ac = AnagramChecker.new
["enlists", "google", "inlets", "banana"].each { |word| ac.add_word word }

ac.inspect   # {"eilnsst"=>#<Set: {"enlists"}>, "eggloo"=>#<Set: {"google"}>, "eilnst"=>#<Set: {"inlets"}>, "aaabnn"=>#<Set: {"banana"}>}

使用它看起来像：

p ac.find_anagrams("listen")  # ["inlets", "listen"]
p ac.find_anagrams("google")  # ["google"]

如果您不希望目标词包含在输出中，请进行相应的调整。find_anagrams

上一个：如何动态定义哈希中所有键的 setter 方法

下一个：在 Rails 中覆盖继承的控制器方法的一部分

Ruby 字谜拼图

Ruby Anagrams puzzle

评论

评论