class Solution:
# @return a list of strings, [s1, s2]
def letterCombinations(self, digits):
if '' == digits: return []
kvmaps = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
return reduce(lambda acc, digit: [x + y for x in acc for y in kvmaps[digit]], digits, [''])
One line python solution


Here is another version:
def letterCombinations(self, digits): map = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'} if len(digits) == 0: return [] return [a+b for a in self.letterCombinations(digits[:1]) for b in self.letterCombinations(digits[1] )] or list(map[digits])
Anybody know a way to get rid of the line "if len(digits) == 0: return []"?

hi, totolipton,here is my solution which i think has 'get rid of the line'.
class Solution(object): def letterCombinations(self, digits): dic = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl',\ '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'} return [a+b for a in dic.get(digits[:1],'') for b in self.letterCombinations(digits[1:]) or ['']] or []

Here is my solution with backtracking
def letterCombinations(self, digits): dic = { '1':'*', '2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'qprs', '8':'tuv', '9':'wxyz', '0':' ' } def generate(segment, digits, letter=[]): if not digits: letter.append(segment) return [] for i in dic[digits[0]]: generate(segment+i, digits[1:]) return letter return generate('',digits)

@DaaangKenny ret is not empty. It has an empty string in it. After the first iteration, ret will contains ["a","b","c"] if the first digit is 2

@MinhuiZheng Actually acc is a name of parameter, you could treat it as tempResultArray. After return the [x + y for x in acc for y in kvmaps[digit]], tempResultArray stands for all the possible string up to the current digit.


here is my solution:
class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ numletter = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } letters = [numletter[i] for i in digits] from functools import reduce if digits: if len(digits) == 1: return list(numletter[digits]) else: return reduce((lambda x, y: [i + j for i in x for j in y]), letters) else: return []

Use the Cartesian product in itertools.
class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ if not digits: return [] mapping = {'0':'', '1':'', '2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'} groups = [mapping[d] for d in digits if d != '0' and d != '1'] return [''.join(x) for x in itertools.product(*groups)]