Iggy Iggy - 2 months ago 7
Ruby Question

How to make a hash of all vowels in a string?

I have googled it everywhere (here, here, here) but strangely I could not find it.

I have a string,

str = "make stackoverflow great again"
. How can I make a hash of all the vowel occurrences in that string?
{"a"=>5, "e"=>3, "i"=>1, "o"=>2, "u"=>0}


Right now I have the most obtuse, least-ruby-like method:

def count_vowels(string)
list = {}
a = string.count("a")
e = string.count("e")
i = string.count("i")
o = string.count("o")
u = string.count("u")

list["a"] = a
list["e"] = e
list["i"] = i
list["o"] = o
list["u"] = u

list
end


What is the most ruby-esque way to make a hash of all the vowels in any given string?

Answer

I'm just going to include an O(n) solution since the prior are all O(n^2).

str.gsub(/[^aeiou]/, "").each_char.each_with_object(Hash.new(0)) { |vowel, hash| hash[vowel] += 1 }
=> {"a"=>5, "e"=>3, "o"=>2, "i"=>1}

Determining the Big O notation of this isn't perfect, so bear with me.

Step 1 - O(n)

str.gsub(/[^aeiou]/, "")
=> "aeaoeoeaaai"

This step loops through the string characters and removes consonants. I did my best to try and find the actual runtime of gsub but without doing my own benchmarks I can't really be sure. I found this when originally writing my answer but it is also not ironclad. gsub should find all indexes that match the expression and return those values as a new string.

Step 2 - O(n)

each_char

Simply takes the string returned and returns an Enumerator. Depending on the language, turning a string into an array of strings/chars has at worst a runtime of the length of the string (hence O(n)). With ruby, returning an Enumerator is actually lazily evaluated so you could argue here we're in O(1).

Step 3 - O(n)

each_with_object(Hash.new(0)) { |vowel, hash| hash[vowel] += 1 }

There are multiple sub-steps here:

Step 3a - Instantiate a new Hash object O(1) who's default value is 0.

Step 3b - Assign/find the key (vowel) in the hash - average O(1), worst case O(n)

Step 3c - Increment that value by 1 - O(1)

Step 3d - Loop through each letter - O(n)

So that means from our 3 steps we have O(n) + O(n) + O(n) which is really O(3n) but Big O states we can drop constants like 3 in this instance, so it just becomes O(n).

I myself am also still learning Big O so this explanation could likely use some community input.

Comments