[Leetcode][python] 17 Letter Combinations of a Phone number

problem :

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

 

code:

from collections import defaultdict

# 1. make phone digits hashmap
d = defaultdict()

asciiValue = 97 # 'a'
for key in range(2, 10): # 2..9
    for value in range(0, 3):
        d.setdefault(key, []).append(chr(asciiValue))
        asciiValue += 1
    if key == 7 :
        d.setdefault(key, []).append(chr(asciiValue))
        asciiValue += 1
    elif key == 9:
        d.setdefault(key, []).append(chr(asciiValue))
        asciiValue += 1
 
'''
# debugging - traversal hashmap
for key in d:
    for value in d[key]:
        print(f'{key},{value}')
'''
    
# 2. recursive function
def recursiveFunc(digits, string, stringList):
    print(f'string:{string}')
    # escape condition
    if len(digits)==0:
        stringList.append(string)
        return
    
    #traversal
    key = digits[0]
    print(f'key:{key}')
    for values in d[int(key)]:
        string+=values
        print(f'values:{values}, string:{string}')
        recursiveFunc(digits[1:], string, stringList)
        string = string[0:-1]
        
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result =[]
        recursiveFunc(digits, "", result)
        return result if not result==[""] else []

 

Time Complexity :

O(3^N)

N is the length of digits

 

 

leetcode most votes (python)

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        interpret_digit = {
            '1': '',
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
            '0': ' '}
        all_combinations = [''] if digits else []
        for digit in digits:
            current_combinations = list()
            for letter in interpret_digit[digit]:
                for combination in all_combinations:
                    current_combinations.append(combination + letter)
            all_combinations = current_combinations
        return all_combinations