快速解析字典

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))，因爲排序是限制功能。如果您嘗試使用非常大的anagrams，則會看到O(n)解決方案的性能損失高於預期。

您可以通過比較兩個字符的地圖=>字符計數來計算O(n)解決方案。

肯定有其他與大致相同的工作，複雜的解決方案，但我不認爲你能拿出什麼比計數O(n)

Answer 2

例更快：

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

我需要的東西檢查字謎，以及與此想出了：

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

你可以做到這一點在O(n+m)其中m爲alphabe的長度t

1.創建一個大小等於您的輸入字母大小的數組。

2.初始化數組中的所有值爲'0'。

3.掃描第一個輸入字符串，爲每個字符增加數組中對應的值（如增量數組[0]，如果找到它的字母表中的第一個字母）。

4.對第二個字符串重複相同的操作，除非在這種情況下數組中的值需要遞減。

如果數組中的所有值都是0，那麼這兩個字符串是anagrams，否則它們不是。