这是在编码问题中问我的,我给出了一个丑陋但有效的解决方案.很想看到大师对这个问题的美丽解决方案.
This was asked me in a coding quesiton, and I gave kind of an ugly, though working solution. Would love to see a master's beautiful solution to this question.
给定一个包含字母和数字的字符串,即"abCd1_k",返回每个变体字符串的数组,其中字母大写发生了变化,即,"AbCd1_k", "ABcd1_k"....
Given a string that includes letters and numbers i.e. "abCd1_k", return an array of every variant string with the capitalization of the letters changed, i.e., "AbCd1_k", "ABcd1_k"....
比AbCd1_k"更简单的问题是ab",它应该返回 ->
A more simple problem case then 'AbCd1_k' would be 'ab', which should return ->
['ab', 'Ab', 'aB' 'AB']
['ab', 'Ab', 'aB' 'AB']
在我看来,根据定义,即使是最漂亮的解决方案仍然会具有昂贵的时间复杂度.(最坏的情况是,每个字符可以有 2 个组合,这意味着 2^n 增长).即使这是真的,在 Ruby 中也必须有一种非常漂亮的方法来做到这一点.
It seems to me that even the most beautiful solution will still have an expensive time complexity by definition. (at worst, you could 2 combinations for each character, which would mean 2^n growth). Even if this is true, there must be a really beautiful way to do this in Ruby.
推荐答案这个怎么样:
def case_permutations(string) string .each_char .reduce(['']) do |acc, char_string| acc.flat_map do |prefix| [char_string.upcase, char_string.downcase] .uniq .map do |modified_char| "#{prefix}#{modified_char}" end end end end您不会比 (2^n)*n 时间复杂度做得更好,因为在最坏的情况下,您的返回值将有 2^n 个长度为 n 的项目.
You're not going to do better than (2^n)*n time complexity because your return value will have 2^n items of length n in the worst case.
更多推荐
带有大写和小写字母的字符串的所有可能变体
发布评论