电话号码的字母组合
Letter Combinations of a Phone Number
题目详情
问题：电话号码的字母组合
考察：字符串、递归
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/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. 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"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
解析
思路：建立数字到字母集合的映射，按输入数字回溯构造字符串。每一层选择当前数字对应的一个字母，长度达到输入长度时记录。
复杂度：时间 O(3^a 4^b)，空间为递归深度和输出规模。