6

2 つの文字列が与えられた場合、それらが互いのアナグラムであるかどうかを判断したいと思います。これが私が思いついた解決策です：

# 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)ますか?

4

4 に答える 4

6

O(n*lg(n))並べ替えは制限機能であるため、大きな O にする必要があります。O(n)非常に大きなアナグラムで試してみると、ソリューションの予想よりもパフォーマンスが低下することがわかります。

O(n)文字の2つのマップのカウントを比較することで解決策を実行できます=>文字数。

ほぼ同じ複雑さで機能する他のソリューションは間違いなくありますが、より速く何かを思いつくことはできないと思いますO(n)

于 2013-03-12T23:11:51.290 に答える
3

あなたはO(n+m)mがアルファベットの長さであるところでそれをすることができます

1.入力アルファベットのサイズと同じサイズの配列を作成します。

2.配列内のすべての値を「0」に初期化します。

3.最初の入力文字列をスキャンし、各文字の配列内の対応する値をインクリメントします（アルファベットの最初の文字が見つかった場合は、array [0]をインクリメントします）。

4. 2番目の文字列についても同じことを繰り返しますが、この場合、配列の値をデクリメントする必要があります。

配列内のすべての値が「0」の場合、2つの文字列はアナグラムです。それ以外の場合は、そうではありません。

于 2013-03-13T11:40:09.020 に答える
3

カウントの例:

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 に答える
1

アナグラムをチェックするために何かが必要で、これを思いつきました：

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 に答える