带有大写和小写字母的字符串的所有可能变体

本文介绍了带有大写和小写字母的字符串的所有可能变体的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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.