A Python version based on counting


  • 0
    C

    Here is just a couting solution for this problem. I just enumerate all possibility based on a novel digit. For example if the input string is '23' I will generate (00 10 20 01 11 21 22), every bit digit referring a character (00-ad, 10-bd, and so on)

    class Solution:
        # @return a list of strings, [s1, s2]
        def letterCombinations(self, digits):
            if not digits or digits == "1":
                return [""]
                
            digitmap = {"1":"","2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
            width = len(digits)
            max_list = []
            result = []
            
            #generate the max_list
            for s in digits :
                max_list.append(len(digitmap[s]) - 1)
            
            code_list = [0] * width
            
            while code_list:
                
                temp_s = ""
                for i in range(width) :
                    temp_s += digitmap[digits[i]][code_list[i]]
                
                result.append(temp_s)
                
                code_list = self.generateCode(width, code_list, max_list)
            
            return result
        
        def generateCode(self, width, code_list, max_list):
            
            #reach max one return None
            if code_list == max_list:
                return None
            
            i = 0
            
            while True:
                code_list[i] = code_list[i] + 1
                if code_list[i] > max_list[i]:
                    code_list[i] = 0
                    i = i + 1
                else:
                    break
            
            return code_list

  • 0
    S

    My version which uses combination logic:

    def letterCombinations(self, digits):
        hashed = {'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']}
    
        combo = hashed[digits[0]][:] if digits else [""]
        
        for dig_index in range(1, len(digits)):
          for i in hashed[digits[dig_index]]:
            new_list = combo[:]
            new_list = [j+i for j in new_list if len(j+i) == dig_index+1]
            combo.extend(new_list)
        
        return [j for j in combo if len(j) == len(digits)]

Log in to reply
 

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