题目描述
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
思路
题目描述很明确，给我们一串数字，求它们能组合成多少种英文字符串。数字和英文字符的对应关系如上图所示，是一个手机键盘。并且题目中还有一个限制，就是只会出现 2 - 9 ，也就意味着我们无需考虑特殊字符。看到组合这两个关键字，我们就应该想到用回溯法，因为回溯一共可以解决 5 类问题：排列、组合、切割、子集、棋盘。
既然确定了是用回溯法，接下来我们来看回溯函数要怎么写，这里我们分三步：
- 确定参数：由于我们要遍历
digits并且每一个字符就是递归树向下的扩展点，因此需要一个index参数来指示当前的字符下标，同时也是树的深度。 - 确定终止条件：对于递归的退出条件，如果当前树的深度已经和
digits的长度相等了，则说明我们已经来到了叶子节点，收集结果并退出。 - 确定单层遍历逻辑：首先我们要取到当前
index对应的数字，并知道该数字都可以表示哪些英文字符。之后对于每个英文字符，都在递归树中构造一个分支。当处理完这个数字之后，还要把path还原。
参考代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
phone = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
res = []
path = []
def backtracking(start):
if len(path) == len(digits):
res.append(''.join(path))
return
for i in range(start, len(digits)):
digit = digits[i]
# 对于每一个字符, 遍历它对应的 letter
for c in phone[digit]:
path.append(c)
backtracking(i + 1)
path.pop()
backtracking(0)
return res
关于复杂度分析，由于最坏的情况下一个数字可以代表 4 个英文字符，假设 digits 的长度为 N，则递归树的每一层都是 4 个分支，一共 N 层。因此时间复杂度为 O(4^N)。递归树深度等于栈的深度，则空间复杂度为 O(N)。
网友评论