快速的字谜解决

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:按字母顺序对字符串进行排序,我不知道如何在Ruby中实现排序,但我认为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)