Python Recursion 55ms


  • 0
    L
    hash_table = {'1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    class Solution:
        # @param digits, a string
        # @return a string[]
        @staticmethod
        def _letterCombinations(determined, digits, res):
            if digits != '':
                digit = digits[0]
                for char in hash_table[digit]:
                    Solution._letterCombinations(determined+char, digits[1:], res)
            else:
                res.append(determined)
    
        def letterCombinations(self, digits):
            res = []
            Solution._letterCombinations('', digits, res)
            return res

  • 0
    S
    enter code here
    digi2le={'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']}
    class Solution:
    # @param {string} digits
    # @return {string[]}
    def letterCombinations(self, digits):
    	if len(digits)==0:
    		return []
    	out=digi2le[digits[0]]
    	
    	for i in xrange(len(digits)-1):
    		curle=digi2le[digits[i+1]]
    		out=reduce(lambda x,y:x+y,[map(lambda x:old+x,curle) for old in out])
    	
    	return out

  • 0
    L

    Using 1 parameter in the recursive function to save space.

    hash_table = {'1':'','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    class Solution:
        # @param digits, a string
        # @return a string[]
        def _letterCombinations(self,digits):
            if len(digits) == 1:
                ret = []
                for char in hash_table[digits[0]]:
                    ret.append(char)
                return ret
            else:
                ret = []
                for char in hash_table[digits[0]]:
                    for elt in self._letterCombinations(digits[1:]):
                        ret.append(char+elt)
                return ret
    
        def letterCombinations(self, digits):
            if not digits:
                return []
            return self._letterCombinations(digits)

Log in to reply
 

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