# 0017. 电话号码的字母组合 ## 题目地址(17. 电话号码的字母组合) <https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number> ## 题目描述 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。  ``` <pre class="calibre18">``` 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例: 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 ``` ``` ## 前置知识 - 回溯 ## 公司 - 阿里 - 百度 - 字节 - 腾讯 ## 思路 使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。究其本质，其实就是枚举。 如果没有更多的数字需要被输入，说明当前的组合已经产生。 如果还有数字需要被输入： - 遍历下一个数字所对应的所有映射的字母 - 将当前的字母添加到组合最后，也就是 str + tmp\[r\] ## 关键点 - 回溯 - 回溯模板 ## 代码 - 语言支持：JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {string} digits * @return {string[]} */</span> <span class="hljs-keyword">const</span> letterCombinations = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">digits</span>) </span>{ <span class="hljs-keyword">if</span> (!digits) { <span class="hljs-keyword">return</span> []; } <span class="hljs-keyword">const</span> len = digits.length; <span class="hljs-keyword">const</span> map = <span class="hljs-keyword">new</span> <span class="hljs-params">Map</span>(); map.set(<span class="hljs-string">"2"</span>, <span class="hljs-string">"abc"</span>); map.set(<span class="hljs-string">"3"</span>, <span class="hljs-string">"def"</span>); map.set(<span class="hljs-string">"4"</span>, <span class="hljs-string">"ghi"</span>); map.set(<span class="hljs-string">"5"</span>, <span class="hljs-string">"jkl"</span>); map.set(<span class="hljs-string">"6"</span>, <span class="hljs-string">"mno"</span>); map.set(<span class="hljs-string">"7"</span>, <span class="hljs-string">"pqrs"</span>); map.set(<span class="hljs-string">"8"</span>, <span class="hljs-string">"tuv"</span>); map.set(<span class="hljs-string">"9"</span>, <span class="hljs-string">"wxyz"</span>); <span class="hljs-keyword">const</span> result = []; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">generate</span>(<span class="hljs-params">i, str</span>) </span>{ <span class="hljs-keyword">if</span> (i == len) { result.push(str); <span class="hljs-keyword">return</span>; } <span class="hljs-keyword">const</span> tmp = map.get(digits[i]); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> r = <span class="hljs-params">0</span>; r < tmp.length; r++) { generate(i + <span class="hljs-params">1</span>, str + tmp[r]); } } generate(<span class="hljs-params">0</span>, <span class="hljs-string">""</span>); <span class="hljs-keyword">return</span> result; }; ``` ``` **复杂度分析** N + M 是输入数字的总数 - 时间复杂度：O(3^N \* 4^M) - 空间复杂度：O(3^N \* 4^M) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。