快速解算

Question

给出两个字符串，我想确定它们是否是对方的字谜。以下是我想出的解决方案：

# output messages
def anagram
    puts "Anagram!"
    exit 
end

def not_anagram
    puts "Not an anagram!"
    exit
end

# main method
if __FILE__ == $0
   # read two strings from the command line
   first, second = gets.chomp, gets.chomp

   # special case 1
   not_anagram if first.length != second.length

   # special case 2
   anagram if first == second

   # general case
   # Two strings must have the exact same number of characters in the
   # correct case to be anagrams.
   # We can sort both strings and compare the results
   if first.chars.sort.join == second.chars.sort.join
      anagram
   else
      not_anagram
   end
end

但我想也许还有更好的办法。我分析了这个解决方案的效率，并提出了：

• chars：将字符串拆分为字符O(n)数组
• sort：按字母顺序排序字符串，我不知道排序是如何在O(n log n)中实现的，但我假设是O(n log n)，因为这是最广为人知的排序效率
• join：从字符O(n)数组构建一个字符串
• ==：字符串比较本身必须检查字符串2*O(n)的每个字符

鉴于以上所述，我将整个解决方案的效率归类为O(n log n)，因为排序效率最高。有比O(n log n)更有效的方法吗？

Answer 1

您的大O应该是O(n*lg(n))，因为排序是限制函数。如果您尝试使用非常大的字谜，您将看到性能损失高于预期的O(n)解决方案。

您可以通过比较两个字符映射中的计数来完成O(n)解决方案，=>字符计数。

当然还有其他的解决方案可以以大致相同的复杂度工作，但我认为您不能想出比O(n)更快的解决方案

Answer 2

计数的例子：

def anagram?(str_a, str_b)
  if str_a.length != str_b.length
    false
  else
    counts = Hash.new(0)
    str_a.each_char{ |c| counts[c] += 1 }
    str_b.chars.none?{ |c| (counts[c] -= 1) < 0 }
  end
end

anagram? 'care', 'race'
# => true
anagram? 'cat', 'dog'
# => false

Answer 3

您可以在O(n+m)中这样做，其中m是字母表的长度

1.创建一个大小与输入字母表大小相等的数组。

2.将数组中的所有值初始化为“0”。

3.扫描第一个输入字符串，为每个字符在数组中增加相应的值(如在找到的字母表中的第一个字母为增量数组)。

4.对第二个字符串重复相同的操作，但在这种情况下，数组中的值需要减少。

如果数组中的所有值都是'0's，那么这两个字符串就是字谜，否则就不是。