Implement a method for ordered_vowel_words
I've been going over some of the many coding interview questions. I was wondering about implementing an ordered_vowel words method. I'm working on algorithm question to implement this method for purposes of the understanding algorithm. I have the below:
This method takes a string of lowercase words and returns a string with just the words containing all their vowels (excluding "y") in alphabetical order. Vowels may be repeated (
"afoot"def ordered_vowel_words(str)
words = str.split(" ")
ordered_vowel_words = words.select do |word|
ordered_vowel_word?(word)
end
ordered_vowel_words.join(" ")
end
def ordered_vowel_word?(word)
vowels = ["a", "e", "i", "o", "u"]
letters_arr = word.split("")
vowels_arr = letters_arr.select { |l| vowels.include?(l) }
(0...(vowels_arr.length - 1)).all? do |i|
vowels_arr[i] <= vowels_arr[i + 1]
end
end
I added the following test cases:
puts("\nTests for #ordered_vowel_words")
puts("===============================================")
puts "ordered_vowel_words(\"amends\") == \"amends\": " + (ordered_vowel_words("amends") == "amends").to_s
puts "ordered_vowel_words(\"complicated\") == \"\": " + (ordered_vowel_words("complicated") == "").to_s
puts "ordered_vowel_words(\"afoot\") == \"afoot\": " + (ordered_vowel_words("afoot") == "afoot").to_s
puts "ordered_vowel_words(\"ham\") == \"ham\": " + (ordered_vowel_words("ham") == "ham").to_s
puts "ordered_vowel_words(\"crypt\") == \"crypt\": " + (ordered_vowel_words("crypt") == "crypt").to_s
puts "ordered_vowel_words(\"o\") == \"o\": " + (ordered_vowel_words("o") == "o").to_s
puts "ordered_vowel_words(\"tamely\") == \"tamely\": " + (ordered_vowel_words("tamely") == "tamely").to_s
What is the runtime analysis for this one?
Why is it true that we can get O(m)O(m) runtime for mm function calls.
I appreciate your explanation for this. thank you.
This method is short and should be reasonably readable :
def ordered_vowel_words(str)
str.split(" ").select{|w| ordered_vowel_word?(w) }.join(" ")
end
def ordered_vowel_word?(word)
vowels = word.scan(/[aeiou]/)
vowels == vowels.sort
end
It might not be very efficient to sort an array just to check it's already sorted, so here's an alternative :
def ordered_vowel_word?(word)
word.scan(/[aeiou]/).each_cons(2).all?{ |vowel1, vowel2| vowel1 <= vowel2 }
end
With this method, the whole complexity should be O(n), n being the number of characters in str.
Complexity cannot be any better, because the whole string needs to be parsed at least once to find the vowels. There might be faster implementations, though.