LC 0784 [M] Letter Case Permutation - ALawliet/algorithms GitHub Wiki

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        def dfs(i, path):
            if i == len(s):
                res.append(path)
            else:
                if s[i].isalpha():
                    dfs(i + 1, path + s[i].upper())
                    dfs(i + 1, path + s[i].lower())
                elif s[i].isdigit():
                    dfs(i + 1, path + s[i])
        
        res = []
        dfs(0, '')
        return res

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        def helper(idx, soFar):
            if idx == len(S):
                coll.append(soFar)
            else:
                if S[idx].isalpha():
                    helper(idx + 1, soFar + S[idx].upper())
                    helper(idx + 1, soFar + S[idx].lower())
                elif S[idx].isdigit():
                    helper(idx + 1, soFar + S[idx])
        
        coll = []
        helper(0, '')
        return coll

- Time Complexity
  - # of calls (decision tree) * amount of work/call (code)
- Space complexity
  - Explicit (collector) + Implicit (stack)

time
worst case: if it was all letters, 2 branches for each letter * n number of letters = 2^n leaf nodes
that just gives the leaves, but everything above that is also 2^n so = 2^n+1
# of calls = 2^n+1

amount of work for copying strings is soFar + cur = n

O(2^n+1 * n) = O(2^n * n)

space
explicit = 2^n possible strings of size n = 2^n * n
implicit = depth of tree and how much space used at each level = n^2 (we can optimize by using an mutable data structure instead of immutable so we don't have to copy the string, then it gets reduced to just n)

O(2^n*n + n^2)