CODEWITHSUNDEEP
ruby
Stepan Parunashvili
Stepan Parunashvili

Reputation: 2845

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.

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"....

A more simple problem case then 'AbCd1_k' would be 'ab', which should return ->

['ab', 'Ab', 'aB' 'AB']

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.

Upvotes: 0

Views: 950

Answers (4)

DavidCQ
DavidCQ

Reputation: 1

How about:

class String
  def case_combinations
    downcased = self.downcase
    [0, 1].repeated_permutation(self.size).to_a.map do |binary_casing|
      permutation = downcased.dup
      binary_casing.each_with_index.map do |binary_case, index|
        permutation[index] = permutation[index].upcase if binary_case == 1
      end
      permutation
    end
  end
end

Basically it creates all possible combinations of 0 and 1 given a length of string, taking that it takes the 1s as representing upcase.

'abc'.case_combinations # ["abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", "ABC"]

If some characters are not letters, it would return duplicates but adding uniq would fix it.

Upvotes: 0

Juan Furattini
Juan Furattini

Reputation: 803

def every_combination(str = '')
  return unless str
  str.chars.permutation(str.size).map do |perm|
    perm_char_case_pair = perm.map do |c|
      [c.downcase, c.upcase]
    end
    perm_char_case_pair[0].product(*perm_char_case_pair[1..-1]).map(&:join)
  end.flatten.uniq
end

Upvotes: 0

limekin
limekin

Reputation: 1944

def case_combos(str)
    c = str.split('').map { |x| [x.upcase, x.downcase]}
    (0...1<<str.size).to_a.map do |x|
        z = ""
        0.upto(c.size-1) do |y|
            z += c[y][0] if (1<<y)&x == 0
            z += c[y][1] if (1<<y)&x != 0
        end
        z
    end.uniq
end

Upvotes: 2

econerd4ever
econerd4ever

Reputation: 111

How about this:

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

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.

Upvotes: 5

Related Questions