LeetCode刷题笔记第17题：电话号码的字母组合
LeetCode刷题笔记第17题：电话号码的字母组合
题目：
想法：
先构建手机号码的字典，利用回溯的思想，组合数字对应的字母，代码如下：
class Solution:def letterCombinations(self, digits: str) -> List[str]:phone = {"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"]}def backtrack(now, next_digits):if not next_digits:ans.append(now)else:for d in phone[next_digits[0]]:backtrack(now + d, next_digits[1:])ans = []if digits:backtrack("", digits)return ans
时间复杂度为： O ( 4 n ) O(4^n) O(4n)，其中n为digits的长度
空间复杂度为： O ( n ) O(n) O(n)，回溯时函数递归的深度