Friedrich Ewald My Personal Website

Leetcode: Letter case permutation

The task is to print all case permutations of letters from strings that can include digits and letters. For example, a1b becomes a1b, a1B, A1b, A1B. The trick here is to realize that there are 2^n possible permutations where n is the number of characters, excluding digits. One possible solution is shown below. The main idea is to generate binary numbers and then use the 1 and 0 in their places to either make the character uppercase or keep it lowercase. For example a decimal number 2 is represented by b10 in binary notation. The number 3 is represented by b11, and so on. When left padding - meaning to write a prefix of 0, all possible combinations are found.

from typing import List

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
      output = []
      s = s.lower()
      n = sum([1 if c.isalpha() else 0 for c in s])
      for i in range(2**n):
        m = f'{bin(i)[2:]:0>{n}}'
        t = ''
        counter = 0
        for c in s:
          if c.isalpha():
            t += c.upper() if m[counter] == '1' else c
            counter += 1
            t += c
      return output
Runtime: 106 ms, faster than 33.96% of Python3 online submissions for Letter Case Permutation. Memory Usage: 14.6 MB, less than 81.20% of Python3 online submissions for Letter Case Permutation.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.