One line python solution


  • 47
    H
    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, [''])

  • 0
    V

    Nice use of reduce


  • 7
    T

    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 []"?


  • 0
    A

    Nice solution. Open minded.


  • 0
    M

    Very concise solution! But could you please enlighten me a little bit about the lambda expression, especially the acc? Thanks!


  • 0

    Sorry, could you explain you code more clearly, you code is great but I could't understand it.
    Thank you for your patience!


  • 2
    H

    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 []

  • 0
    H

    It's a functional way which uses a middle variable to make the recursion possible.


  • 18
    B

    Here is another version without reduce:

    if '' == digits: return []
        kvmaps = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        ret=['']
        for c in digits:
            tmp=[]
            for y in ret:
                for x in kvmaps[c]:
                    tmp.append(y+x)
            ret=tmp
        
        return ret

  • 0
    D

    Hey there, for the first time you run through the loop shouldn't ret be empty?

    what is happening in the first iteration of "for y in ret"


  • 0
    G

    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)
    

  • 0

    Impressive idea!


  • 0
    L

    the two line in your code containing "temp" can be deleted at all. It is unnecessary


  • 0
    G

    Thanks a lot!!!


  • 0
    L

    @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


  • 0
    H

    @wave This is the problem with the one-liners


  • 0
    I

    @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.


  • 0
    C

    @totolipton map is reserved key word.


  • 1
    L

    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 []
    

  • 0
    S

    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)]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.