Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.



Example:


Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].


Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Difficulty: interview

Starter code:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        

Solutions:
class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         
         def dfs(digits, current, result):
             if not digits:
                 result.append(current)
                 return
             for c in dic[digits[0]]:
                 dfs(digits[1:], current + c, result)
         
         
         if not digits:
             return []
         
         dic = { '2' : "abc", '3': "def", '4':"ghi", 
                '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv",'9': "wxyz" }
         result = []
         dfs(digits, "", result)
         return result
         
         
         
 


class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         if not digits:
             return []
         MAPPING = ('0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz')
         def directed_combinations(i, partial):
             if i == len(digits):
                 result.append(''.join(partial))
                 return
             
             for c in MAPPING[int(digits[i])]:
                 directed_combinations(i + 1, partial + [c])
         
         result = []
         directed_combinations(0, [])
         return result

class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         
         dic = {'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 '0' in digits:
             digits = digits.replace('0','')
         if '1' in digits:
             digits = digits.replace('1','')
         
         count = 0
         for a in '23456789':
             if a not in digits:
                 count += 1
         if count == 8:
             return []
         
     
         res = []
         
         temp = ['']
         i = 0
         while i < len(digits):
             for a in temp:
                 for b in dic[digits[i]]:
                     res.append(a+b)
             temp = res
             res = []
             i += 1
         return temp
         
         
         
         
         


class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         if '' == digits: 
             return []
         
         kvmaps = {
             '2': 'abc',
             '3': 'def',
             '4': 'ghi',
             '5': 'jkl',
             '6': 'mno',
             '7': 'pqrs',
             '8': 'tuv',
             '9': 'wxyz'
         }
         rst = ['']
         for digit in digits:
             temp = [s + c for s in rst for c in kvmaps[digit]]
             rst = temp
         
         return rst


class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         if digits==None or len(digits) ==0:
             return []
         res=[]
         cur=""
         dmap={}
         dmap["0"]=[" "]
         dmap["1"]=[]
         dmap["2"]=["a","b","c"]
         dmap["3"]=["d","e","f"]
         dmap["4"]=["g","h","i"]
         dmap["5"]=["j","k","l"]
         dmap["6"]=["m","n","o"]
         dmap["7"]=["p","q","r","s"]
         dmap["8"]=["t","u","v"]
         dmap["9"]=["w","x","y","z"]
         self.dfs(digits,dmap,0,cur,res)
         return res
     
     def dfs(self,digits,dmap,idx,cur,res):
         if idx ==len(digits):
             res.append(cur)
             return
         else:
             c=digits[idx]
             for i in dmap[c]:
                 self.dfs(digits,dmap,idx+1,cur+i,res)


from functools import reduce
 
 class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         
         d = {}
         d["1"] = ""
         d["2"] = "abc"
         d["3"] = "def"
         d["4"] = "ghi"
         d["5"] = "jkl"
         d["6"] = "mno"
         d["7"] = "pqrs"
         d["8"] = "tuv"
         d["9"] = "wxyz"
         d["0"] = " "
         
         digs = list(map(lambda x: list(d[x]), digits))
         
         return reduce(alg_mul, digs, [])
                 
 
 def alg_mul(xs, ys):
     if xs == []:
         return ys
     
     ws = []
     for x in xs:
         for y in ys:
             ws.append(x + y)
     
     return ws

import queue
 class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         letterDict = {0:[],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 len(digits) == 0:
             return []
         res = [""]
         for i in range(len(digits)):
             num = int(digits[i])
             chars = letterDict[num]
             if len(chars) == 0:
                 continue
             s = []
             for j in range(len(chars)):
                 for k in range(len(res)):
                     s.append(res[k] + chars[j])
             res = s
         return res
                     

import heapq
 
 
 class Solution:
     def letterCombinations(self, digits):
         digit_map = {'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'],
                     '0': [""]}
         combs = []
         # Queue will hold a list of tuples mapping to how many characters are already mapped, 
         # and the current converted string!
         letter_q = [(0, "")]
         if not digits:
             return []
         while letter_q:
             cur = heapq.heappop(letter_q)
             cur_idx = cur[0]
             cur_str = cur[1]
             next_dig = digits[cur_idx]
             for value in digit_map[next_dig]:
                 new_digit_str = (cur_idx+1, cur_str+value)
                 if cur_idx + 1 >= len(digits):
                     combs.append(new_digit_str)
                 else:
                     heapq.heappush(letter_q, new_digit_str)    
         return list(map(lambda x: x[1], combs))

class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         key = {2:'abc', 3:'def', 4:'ghi',5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}
     
         nonlocal out
         out = ['']
 
         def eachLetter(i):
             if i < len(digits):
                 nonlocal out
                 if int(digits[i]) > 1:
                     x = []
                     for j in out:
                         for k in key[int(digits[i])]:
                             x.append(j+k)
                     out = x
 
                 eachLetter(i+1)
 
         eachLetter(0)
         
         return [] if out[0] is '' else out


from collections import defaultdict
 
 class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         digit_to_chars = defaultdict(list)
         char_int = ord('a')
         for i in range(2,10):
             num_chars = 3 if i not in {7,9} else 4
             for j in range(num_chars):
                 digit_to_chars[str(i)].append(chr(char_int))
                 char_int += 1
         if not digits:
             return []
         letter_combinations = ['']
         for digit in digits:
             new_letter_combinations = []
             for letter_combination in letter_combinations:
                 for character in digit_to_chars[digit]:
                     new_letter_combination = letter_combination + character
                     new_letter_combinations.append(new_letter_combination)
             letter_combinations = new_letter_combinations
         return letter_combinations

class Solution:
     Dmap = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno',
              '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
     
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         if '1' in digits or '0' in digits:
             return []
         
         if len(digits) == 0:
             return []
         
         return self.letterC(digits)
 
         
     def letterC(self, digits):
         if len(digits) == 0:
             return ['']
         
         res = []
         for back in self.letterC(digits[1:]):
             for fr in self.Dmap[digits[0]]:
                 res.append(fr + back)
         
         return res


class Solution:
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         self.dic={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
         if not digits:
             return []
         res = []
         self.dfs(digits,0,'',res)
         return res
     
     def dfs(self, digits, index, path, res):
         if len(path) == len(digits):
             res.append(path)
             return
         for i in range(len(self.dic[digits[index]])):
             path_ = path+self.dic[digits[index]][i]
             self.dfs(digits,index+1,path_,res)
         
         


class Solution:
     def __init__(self):
         self.phone = ["", "", "abc", "def","ghi", "jkl", "mno", "pqrs","tuv", "wxyz"]
         
     def letterCombinations(self, digits):
         """
         :type digits: str
         :rtype: List[str]
         """
         
         if not digits:
             return []
         
         results = []
         self.dfs(digits, results, "", 0)
         return results
     
 
     def dfs(self, digits, results, string, index):
         if index == len(digits):
             results.append(string)
         else: 
             letters = self.phone[int(digits[index])]    
            
             for i in range(0, len(letters)):
                 self.dfs(digits, results, string + letters[i], index + 1)
 
         
     


class Solution:
     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