17. Letter Combinations of a Phone Number (Python) dfs(递归 recursion) + 迭代（iterative）

17. Letter Combinations of a Phone Number

Medium

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

 

 

笔记：

方法1：dfs

DFS 其实就是穷举，当需要穷举某一个东西时，可以考虑DFS。但是当穷举量特别大的时候，就合适，会发生栈溢出，这时候就需要通过动态规划来解决。

这个题目其实就是穷举出所有的可能，所以可以用DFS。下面图片展示了DFS的树结构

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        num_letter = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                      '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        rlt = []
        self.dfs(0, rlt, digits, num_letter, '')
        return rlt

    def dfs(self, level, rlt, dig, num_to_letter, pre_letter):
        if level == len(dig):
            rlt.append(pre_letter)
            return
        letters = num_to_letter[dig[level]]
        for letter in letters:
            temp = pre_letter + letter
            self.dfs(level + 1, rlt, dig, num_to_letter, temp)

运行时间：

 

方法2：迭代

其实就是找规律，找出可以迭代的规律。用一个list里面跟后面一个list里面的字母结合，组成新的list，然后用新的list去再跟下一个list结合。

运行时间：

class Solution:
    def letterCombinations(self, digits: str):
        num_letter = {'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']}

        if not digits:
            return []
        rlt = num_letter[digits[0]]
        for digit in digits[1:]:
            temp = []
            for num1 in rlt:
                for num2 in num_letter[digit]:
                    temp.append(num1 + num2)
            rlt = temp
        return rlt