class Solution:
def letterCombinations(self, digits: str) -> List[str]:
"""
main idea: typical backtracking problem to choose all char in first digit while track remaining substring.
step0: edge case: if digits is "" return immediately
step1, cache all characters corresponding to digit and set res []
step2, termination check: when there is no substring. then put all combinations into res
step3, for first digit of current input digits, loop through all char in the _map to get all the possible choices
step4, go to next level of recursion with updated new path and remaining substring digits.
time O(4^L * 3^M) space O(4^L * 3^M)
"""
if len(digits) == 0:
return []
_map = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
res = []
def btr(subs,path):
if subs == "":
res.append(path[:])
return
for ch in _map[subs[0]]:
btr(subs[1:],path+ch)
btr(digits,"")
return res
iterative
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
#time O(4^L * 3^M) space O(4^L * 3^M)
if len(digits) == 0:
return []
_map = {'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']}
res = ['']
def helper(di):
path = []
for each_combine in res:
for ch in _map[di]:
path.append(each_combine+ch)
return path
for digit in digits:
res = helper(digit)
print(res)
return res