6

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

# 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)

Given the above, I categorized the efficiency of the entire solution as O(n log n) since sorting had the highest efficiency. Is there a better way to do this that is more efficient than O(n log n)?

4

4 回答 4

6

Your big O should be O(n*lg(n)) since the sort is the limiting function. If you try it with very big anagrams you will see a loss of performance higher than expected for an O(n) solution.

You can do an O(n) solution by comparing counts in two maps of characters => character counts.

There are definitely other solutions that work with approximately the same complexity but I don't think you can come up with anything faster than O(n)

于 2013-03-12T23:11:51.290 回答
3

Example of counting:

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
于 2013-03-12T23:43:38.207 回答
3

You can do it in O(n+m) where m is length of alphabet

1.Create an array of size equal to the size of your input alphabet.

2.Initialize all the values in the array to '0'.

3.Scan the first input string, increment the corresponding value in the array for each character (like increment array[0] if first letter in the alphabet it found).

4.Repeat the same for the second string, except in this case the value in the array need to be decremented.

If all the values in the array are '0's then the two strings are anagrams, else they are not.

于 2013-03-13T11:40:09.020 回答
1

I needed something to check anagrams, and came up with this:

def string_to_array(s)
  s.downcase.gsub(/[^a-z]+/, '').split('').sort
end

def is_anagram?(s1, s2)
  string_to_array(s1) == string_to_array(s2)
end

puts is_anagram?("Arrigo Boito",       "Tobia Gorrio")
puts is_anagram?("Edward Gorey",       "Ogdred Weary")
puts is_anagram?("Ogdred Weary",       "Regera Dowdy")
puts is_anagram?("Regera Dowdy",       "E. G. Deadworry")
puts is_anagram?("Vladimir Nabokov",   "Vivian Darkbloom")
puts is_anagram?("Vivian Darkbloom",   "Vivian Bloodmark")
puts is_anagram?("Dave Barry",         "Ray Adverb")
puts is_anagram?("Glen Duncan",        "Declan Gunn")
puts is_anagram?("Damon Albarn",       "Dan Abnormal")
puts is_anagram?("Tom Cruise",         "So I'm cuter")
puts is_anagram?("Tom Marvolo Riddle", "I am Lord Voldemort")
puts is_anagram?("Torchwood",          "Doctor Who")
puts is_anagram?("Hamlet",             "Amleth")
puts is_anagram?("Rocket boys",        "October Sky")
puts is_anagram?("Imogen Heap",        "iMegaphone")
于 2013-03-13T06:02:50.957 回答