https://leetcode.com/problems/letter-case-permutation

In this problem we need to generate all possible letter case permutations, and let us first underatand how many of them we have. If we have digit, we have only 1 option: we need to choose this digit. If we have letter: we have 2 options: choose either small or capital letter. So, if we have m letters, there will be O(2^m) different solutions. When you have a lot of different solutions, it is is a good indicator that it is backtracking problem.

So, let us use dfs(i, built) function, where:

  1. i is current number of symbols we are processing and
  2. built is string built so far.

If we have next symbols which is letter, we need to consider two options, if it is digit, only one.

Complexity is O(2^m*k), where m is number of letters and k is length of all string: we have 2^m solutions, each of them has length k, and what is important we never go to deadend, so all solutions we are trying to build will be added to final answer. Space complexity is O(2^m*k) as well.

class Solution:
    def letterCasePermutation(self, S):
        def dfs(i, built):
            if i == len(S):
                self.ans.append(built)
                return
            if S[i].isalpha():
                dfs(i+1, built + S[i].lower())
            dfs(i+1, built + S[i].upper())
        
        self.ans = []
        dfs(0, "")
        return self.ans

Solution 2: using product

Another solution is to use product functionality from python: complexity is the same but it can work a bit faster do to low-level optimizations.

class Solution:
    def letterCasePermutation(self, S):
        return map(''.join, product(*[set([i.lower(), i.upper()]) for i in S]))

If you like the solution, you can upvote it on leetcode discussion section: Problem 0784