Szybkie rozwiązywanie anagramów

Question

Biorąc pod uwagę dwa ciągi, chciałbym określić, czy są one wzajemnie anagramami. Oto rozwiązanie, które wymyśliłem:

# 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 

Ale myślę, że prawdopodobnie jest lepszy. I analizowano skuteczność tego rozwiązania, i wymyślił:

• chars: dzieli ciąg na tablicę znaków O(n)
• sort: sortuje ciąg alfabetycznie, nie wiem jaki rodzaj jest realizowany w Ruby, ale zakłada O(n log n) ponieważ jest to ogólnie najlepiej znane sortowania wydajność
• join: buduje ciąg z tablicy znaków O(n)
• ==: porównanie ciąg sama będzie musiała zbadać każdy znak strun 2*O(n)

Biorąc powyższe pod uwagę, że na kategorie wydajności całego rozwiązania jak O(n log n) od sortowania miał najwyższą wydajność. Czy istnieje lepszy sposób na zrobienie tego, który jest bardziej wydajny niż O(n log n)?

Answer 1

Twoje duże O powinno być O(n*lg(n)), ponieważ sort jest funkcją ograniczającą. Jeśli spróbujesz go z bardzo dużymi anagramami, zobaczysz stratę wydajności wyższą od oczekiwanej dla rozwiązania O(n).

Możesz zrobić rozwiązanie O(n), porównując liczby na dwóch mapach znaków => liczba znaków.

Na pewno są inne rozwiązania, które działają z mniej więcej taką samą złożoność, ale nie sądzę, że można wymyślić coś szybszego niż O(n)

Answer 2

Przykład liczenia:

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

potrzebowałem czegoś by sprawdzić anagramy i podszedł z tym:

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

Answer 4

można to zrobić w O(n+m) gdzie m jest długość alphabe t

1.Utwórz tablicę o rozmiarze równym rozmiarowi wprowadzonego alfabetu.

2.Zainicjalizuj wszystkie wartości w tablicy na "0".

3. Zeskanuj pierwszy ciąg wejściowy, zwiększając odpowiednią wartość w tablicy dla każdego znaku (np. W tablicy przyrostowej [0], jeśli pierwsza litera znalezionego alfabetu).

4. Powtórz to samo dla drugiego ciągu, z tą różnicą, że wartość w tablicy musi być zmniejszona.

Jeśli wszystkie wartości w tablicy są równe 0, to dwa ciągi są anagramami, inaczej nie są.