17. Letter Combinations of a Phone Number

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.

这道题是典型的回溯法：固定一个节点，遍历可能的下一层直到全部遍历结束，回到上一层的节点，找到下一个节点继续遍历。

借鉴这个博客里的简介

https://segmentfault.com/a/1190000006121957

判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。

一般回溯的问题有三种：

1. Find a path to success 有没有解
2. Find all paths to success 求所有解
   • 求所有解的个数
   • 求所有解的具体信息
3. Find the best path to success 求最优解

理解回溯：给一堆选择, 必须从里面选一个. 需要遍历所有选择/选完之后需要从同一个node开始选别的选项. 这个过程一直重复知道你达到了终止条件（final state）。如果这个终止的结果满足条件，那么我们就得到了其中一个结果。

回溯可以抽象为一棵树，我们的目标可以是找这个树有没有good leaf，也可以是问有多少个good leaf，也可以是找这些good leaf都在哪，也可以问哪个good leaf最好，分别对应上面所说回溯的问题分类。

回溯问题的重要做法就是lock一个leaf node，如何lock这个node就需要利用到递归。

在这道题上我们首先要把每一个digit代表的字母抽出来，然后lock第一个digit的第一个字母 “a“（ a = KeyboardNumbers[digits[0]])，然后再这种情况下循环下一个digits (3)代表的字母（=“def”)，一直循环到我们找到了一个path，这个path的长度正好等于digits的长度，这说明我们得到了一个满足要求的结果。

鉴于以上的分析，这个递归我们需要

1. 锁定一个字母，也就是我们需要一个index，然后递归的时候index需要 + 1
2. 历史的path，因为我们需要它来判断是否得到一个可以使用满足条件的result

所以 def backtrack(path, i)就确定下来

def backtrack(path, i):
	if len(path) == len(digits):
		result.append(path) # 把path加入到result里面
		return
	else:
		#这里比较难理解，我们需要遍历每一个在这个索引i下面的字母
		for letter in  键盘字母表[digits[i]]:
			backtrack(path + letter, i + 1)
			# 我们把path加上这个letter（比如之前是a，现在是ad）传进去backtrack
			# 再让索引递增1
			# 这样相当于我们锁定了ad，
			# 然后再在下一层，第三个数字（如果有的话）代表的索引下面循环
			# 一直循环到len(path) == len(digits) 我们把结论加到result
			# 再返回到上一层，也就是循环到e，锁定ae，继续重复

def backtrack(path, i):
	if len(path) == len(digits):
		result.append(path) # 把path加入到result里面
		return
	else:
		#这里比较难理解，我们需要遍历每一个在这个索引i下面的字母
		for letter in  键盘字母表[digits[i]]:
			backtrack(path + letter, i + 1)
			# 我们把path加上这个letter（比如之前是a，现在是ad）传进去backtrack
			# 再让索引递增1
			# 这样相当于我们锁定了ad，
			# 然后再在下一层，第三个数字（如果有的话）代表的索引下面循环
			# 一直循环到len(path) == len(digits) 我们把结论加到result
			# 再返回到上一层，也就是循环到e，锁定ae，继续重复

整个解法过程如下

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        length = len(digits)
        dic =  {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(path, i):
            if len(path) == length:
                res.append(path)
                return
            else:
                for letter in dic[digits[i]]:
                    backtrack(path + letter, i+1)
        res = []

        if digits:
            backtrack("", 0)
        return res

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        length = len(digits)
        dic =  {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(path, i):
            if len(path) == length:
                res.append(path)
                return
            else:
                for letter in dic[digits[i]]:
                    backtrack(path + letter, i+1)
        res = []

        if digits:
            backtrack("", 0)
        return res