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
else:
t += c
output.append(t)
return output