-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0784 [M] Letter Case Permutation
Code with Senpai edited this page Jun 20, 2022
·
15 revisions
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)
footer