ruby - 为 ordered_vowel_words 实现一个方法

Question

我已经复习了许多编码面试问题中的一些问题。我想知道如何实现一个 ordered_vowel words 方法。为了理解算法，我正在研究算法问题以实现此方法。我有以下内容:

此方法接受一串小写单词并返回一个字符串，其中仅包含按字母顺序排列的所有元音(不包括“y”)的单词。元音可以重复("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

我添加了以下测试用例:

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

这个的运行时分析是什么？

为什么对于 mm 函数调用我们可以获得 O(m)O(m) 的运行时间。

感谢您对此的解释。谢谢。

Answer 1

这个方法很简短，应该具有合理的可读性:

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

仅仅为了检查它是否已经排序而对数组进行排序可能不是很有效，所以这里有一个替代方案:

def ordered_vowel_word?(word)
  word.scan(/[aeiou]/).each_cons(2).all?{ |vowel1, vowel2| vowel1 <= vowel2 }
end

使用这种方法，整个复杂度应该是O(n)，n是str中的字符数。

复杂度再好不过了，因为整个字符串至少需要解析一次才能找到元音字母。不过，可能会有更快的实现。