17. 电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

解法一：迭代法

如“23”，2对应“abc”，3对应“def”，对每个数字进行遍历。初始结果集为空（用一个空串""表示）

第一轮，i=0，候选集为digits[0]=2，即abc。每轮对结果集的每个元素（此时为唯一元素""）分别添加候选集的每个元素’a’,’b’,’c’，得到新的结果替换原来的结果集，此时结果集=[‘a’,’b’,’c’]

第二轮，i=1，候选集为digits[1]=3，即def。对结果集的每个元素（此时为’a’,’b’,’c’），分别添加候选集的每个元素’d’,’e’,’f’，共得到3*3=9种新结果： [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]，替换原结果集。

以此类推，迭代到最后。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        res = [""]  #初始结果集，有一个空串元素
        v = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        for i in range(len(digits)):  #对每位数字
            dig = int(digits[i])  #先将字符串转为整数
            candidate = v[dig]  #候选集
            newRes = []  #新结果集，初始为空
            #笛卡尔积
            for j in res:
                for k in candidate:
                    newRes.append(j + k)  #候选集每个元素添加到原结果后面，得到新结果
            res = newRes
        return res

解法二：

用python的itertools.product方法生成笛卡尔积。 这个方法的用法如下：输入参数为可变：

for s in itertools.product('abc', 'def'):
    print(s)

输出’abc’, ‘def’的笛卡尔积： (‘a’, ‘d’) (‘a’, ‘e’) (‘a’, ‘f’) (‘b’, ‘d’) (‘b’, ‘e’) (‘b’, ‘f’) (‘c’, ‘d’) (‘c’, ‘e’) (‘c’, ‘f’)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        res = []
        letters = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]  #将所有数字对应的字符分别存入
        return ["".join(s) for s in itertools.product(*[letters[int(dig)] for dig in digits])]

最后return写的较复杂，拆开分析： 首先返回的是一个list。其中有一个空串，每次用空串的join方法写入字符串s。 s是笛卡尔积的结果，笛卡尔积输入的参数是一个解包（py3.5新特性），用for循环将所有串输入。

注意这个*号，是解包的意思，即将列表[]中的参数一个个取出来，否则就是将整个list作为函数的输入。对比下面两段代码：

return ["".join(s) for s in itertools.product(*['abc', 'def'])]

返回[‘ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]

return ["".join(s) for s in itertools.product(['abc', 'def'])]

返回[‘abc’, ‘def’]，一个元素的笛卡尔积等于自身

注意另一个点，[]中嵌套for表达式称为列表推导式，形式如下：

[表达式 for 变量 in 列表]    或者  [表达式 for 变量 in 列表 if 条件]

因为需要对所有digits遍历，需要用到列表推导式，而推导式本身又是一个list[]，因此需要用到解包*。环环相扣。