ruby – 快速的字谜解决

# 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)更有效的方法呢？