带有大写和小写字母的字符串的所有可能变体 [英] All possible variants of a string with capital and lowercase letters

问题描述

这是在编码问题中问我的，我给出了一个丑陋但有效的解决方案.很想看到大师对这个问题的美丽解决方案.

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.

这篇关于带有大写和小写字母的字符串的所有可能变体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！