17. Letter Combinations of a Phone Number

Approach 1: Generating all combinations one by one

class Solution:
def letterCombinations(self, digits):
"""
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
:type digits: str
:rtype: List[str]
"""
mapping = {'1':[],'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']}
if digits == '':
return []
else:
ans = mapping[digits[0]]
for i in range(1,len(digits)):
l = []
for j in mapping[digits[i]]:
for k in ans:
l.append(k+j)
ans = l
return ans

This solution goes over each number in digits and appends the letters on that position to the end of all the existing strings in ans

For example, digits = '23', then ans = ['a','b','c'] # initialised from line 12

In the for loop, I come to '3' and then for every element in ans I append a letter from digit '3' which means ans becomes ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Time Complexity: O(N), where N is the total number of possible combinations that get returned

Space Complexity: O(N)