Leetcode17 Letter Combinations of a Phone Number

Question:

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Thinking

迭代思想！想法：‘2345’代表一个字符串，每一个数字又代表着一个字符列表（如 ‘2’ 代表['a','b','c']这个list）
如果只有'2'这一个数字，那么结果当然就是['a','b','c']这个答案。如果想知道‘23’能组合的字符列表，就把['a','b','c']和['c','d','e']两两组合。'234'就把‘23’得到的结果和'4'代表的list组合。这样就永远只用考虑两个列表的组合。

Codes

 class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        size = len(digits)
        ans = []
        # 从后往前
        for i in range(size - 1, -1, -1):
            l1 = self.GetList(digits[i])
            ans = self.ListsCombinations(l1, ans)
        return ans


    def GetList(self, c):
        ans = []
        if c == '0' or c == '1':
            return ans
        elif c <= '6':
            num = int(c) - 2
            start = ord('a') + num * 3
            for i in range(start, start + 3):
                ans.append(chr(i))
        elif c == '7':
            ans.extend(['p', 'q', 'r', 's'])
        elif c == '8':
            ans.extend(['t', 'u', 'v'])
        elif c == '9':
            ans.extend(['w', 'x', 'y', 'z'])
        return ans



    def ListsCombinations(self, l1, l2):
        size1 = len(l1)
        size2 = len(l2)
        ans = []
        if size1 == 0 or size2 == 0:
            if size1 == 0:
                ans = l2
            else:
                ans = l1
            return ans
        for i in range(size1):
            for j in range(size2):
                ans.append(l1[i] + l2[j])
        return ans

Key Points

# 这是入口
def letterCombinations(self, digits):

# 得到数字字符代表的字符列表 （键盘）
 def GetList(self, c):

 # 组合两个列表
  def ListsCombinations(self, l1, l2):

Performance of Codes:

Pretty Good!