17. 电话号码的字母组合[medium]

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

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

通过次数117,654 提交次数219,492

Second Try

2020-06-05

使用递归DFS的方法搞定，思路挺有意思的，减轻了人脑的负担，让程序去考虑那些边边角角的遍历。这种递归消耗的思路还不太习惯，没有写的经验。

但很奇怪在测试里都可以通过，但是提交总是出错。修改提交后，测试结果在速度和内存占用方面还是没有优势。

class Solution(object):

    rv = []
    kb_digits = ["_", "-", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        self.consump("", digits)
        return self.rv
            
    def consump(self, combine, digits):
        if len(digits) == 0:
            self.rv.append(combine)
            return
        for char in self.kb_digits[int(digits[0])]:
           self.consump(combine + char, digits[1:] ) 

可以上传通过的版本，递归函数写在原来的函数内部。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        rv = []
        kb_digits = ["_", "-", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        def consump(combine, digits):
            if len(digits) == 0:
                rv.append(combine)
                return
            for char in kb_digits[int(digits[0])]:
                consump(combine + char, digits[1:]) 

        if not digits:
            return []
        consump("", digits)
        return rv

执行用时 :24 ms, 在所有 Python 提交中击败了39.62%的用户
内存消耗 :12.8 MB, 在所有 Python 提交中击败了5.26%的用户

First Try

2020-06-05

本来觉得求笛卡尔积很容易，结果怎么都搞不定多重循环。一狠心写成遍历，参照数学加法，每次加一进位，一直到最大值。区别在于每一位取决于其字符串的长度，并不是固定。这前面十几道题，写来写去都是i/j几个参数来回遍历，总感觉不到高级。不过高级结构那些我书都没翻完。。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        kb_digits = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        n = len(digits)
        col = [kb_digits[int(i)-2] for i in digits]
        arr = [len(c) for c in col]
        inc = [0] * len(col) 
        rv = []
        while (inc[-1] < arr[-1]):
            t = ""
            for i in range(n):
                t +=  col[i][inc[i]]
            rv.append(t)
            # step by step
            inc[0] += 1
            for i in range(n):
                # carry 
                if inc[i] >= arr[i]:
                    if i == n - 1:
                        break
                    inc[i] = 0
                    inc[i+1] += 1
                     
        return rv

执行用时 :24 ms, 在所有 Python 提交中击败了39.62%的用户
内存消耗 :12.7 MB, 在所有 Python 提交中击败了5.26%的用户

17. 电话号码的字母组合[medium]​

Second Try​

First Try​

17. 电话号码的字母组合[medium]

Second Try

First Try