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)