Implement a method for ordered_vowel_words

Question

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" is an ordered vowel word)

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.

Answer 1

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.