17. Letter Combinations of a Phone Number

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []

        keypad = {}
        keypad['2'] = "abc"
        keypad['3'] = "def"
        keypad['4'] = "ghi"
        keypad['5'] = "jkl"
        keypad['6'] = "mno"
        keypad['7'] = "pqrs"
        keypad['8'] = "tuv"
        keypad['9'] = "wxyz"

        # get the default letter
        temp = []
        letters = keypad[digits[0]]
        for i in range(0, len(letters)):
            temp.append(letters[i])

        # iterate each digit num
        for i in range(1, len(digits)):

            # Get the letters of the digit num
            s = keypad[digits[i]]

            # Get the num of res
            num = len(temp)

            for j in range(0, len(s)):
                if j == 0:
                    for k in range(num):
                        temp[k] = temp[k] + s[j]
                else:
                    for k in range(num):
                        temp.append(temp[k][:-1] + s[j])

        return temp