2

我已经解决了一个问题，该问题要求您编写一种方法来确定提供的数组中的哪些单词是字谜，并将字谜分组到输出中的子数组中。

我已经使用似乎是典型的方式解决了它，即通过对单词进行排序并根据它们的排序字符将它们分组到哈希中。

当我最初开始寻找一种方法来做到这一点时，我注意到String#sum存在将每个字符的序数加在一起。

我想尝试找出一些方法来确定基于 using 的字谜sum。例如“cars”和“scar”是字谜，它们sum是 425。

给定%w[cars scar for four creams scream racs]预期输出的输入（我已经使用哈希解决方案得到）是：[[cars, scar, racs],[for],[four],[creams,scream]].

似乎在做类似的事情：

input.each_with_object(Hash.new []) do |word, hash|
  hash[word.sum] += [word]
end

是要走的路，它给你一个散列，其中键“425”的值是['cars'，'racs'，'scar']。我认为我缺少的是将其转换为预期的输出格式。

4

4 回答 4

17

不幸的是，我认为这不是String#sum解决此问题的可靠方法。

考虑：

"zaa".sum # => 316
"yab".sum # => 316

相同的总和，但不是字谜。

相反，如何按字符的排序顺序对它们进行分组？

words = %w[cars scar for four creams scream racs]

anagrams = words.group_by { |word| word.chars.sort }.values
# => [["cars", "scar", "racs"], ["for"], ["four"], ["creams", "scream"]]
于 2012-03-01T14:40:27.233 回答
1

要获得所需的输出格式，您只需要hash.values. 但请注意，仅使用单词中字符代码的总和可能会在某些输入上失败。当两个单词不是字谜时，它们的字符代码之和可能偶然相同。

如果您使用不同的算法来组合字符代码，则错误地将单词识别为“字谜”的机会可能会大大降低，但仍不为零。基本上你需要某种散列算法，但具有散列值的顺序无关紧要的属性。也许将每个字符映射到一个不同的随机位串，并为字符串中的每个字符取位串的总和？

这样，任何两个非字谜给你一个误报的机会大约是2 ** bitstring_length.

于 2012-03-01T14:24:09.020 回答
1 
words = %w[cars scar for four creams scream racs]
res={}

words.each do |word|
  key=word.split('').sort.join
  res[key] ||= []
  res[key] << word
end

p res.values


[["cars", "scar", "racs"], ["for"], ["four"],["creams", "scream"]]
于 2012-03-01T15:00:13.190 回答
1

实际上，我认为您可以使用 sums 进行字谜测试，但不能对字符的序数本身求和，而是像这样：

words = %w[cars scar for four creams scream racs]
# get the length of the longest word:
maxlen = words.map(&:length).max
# => 6 
words.group_by{|word|
  word.bytes.map{|b|
    maxlen ** (b-'a'.ord)
  }.inject(:+)
}
# => {118486616113189=>["cars", "scar", "racs"], 17005023616608=>["for"], 3673163463679584=>["four"], 118488792896821=>["creams", "scream"]}

不确定这是否 100% 正确，但我认为逻辑成立。

这个想法是将每个单词映射到一个基于 N 的数字，每个数字位置代表一个不同的字符。N是输入集中最长单词的长度。

于 2012-03-01T16:43:05.197 回答