欢迎来到李耶的频道【LeetCode面试题】。电话号码的字母组合17.电话号码的字母组合题目给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。2: abc 3: def 4: ghi 5: jkl 6: mno 7: pqrs 8: tuv 9: wxyz输入digits 23 输出[ad,ae,af,bd,be,bf,cd,ce,cf]输入digits 输出[]输入digits 2 输出[a,b,c]解法一回溯法DFS思路使用深度优先搜索DFS遍历所有可能的组合。维护一个路径字符串每次递归选择一个数字对应的一个字母直到处理完所有数字。functionletterCombinations(digits){if(!digits||digits.length0)return[];constmap{2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz};constresult[];functionbacktrack(index,path){if(indexdigits.length){result.push(path);return;}constlettersmap[digits[index]];for(constletterofletters){backtrack(index1,pathletter);}}backtrack(0,);returnresult;}时间复杂度 / 空间复杂度O(3^m × 4^n) / O(m n)其中 m 是 3 个字母的数字个数n 是 4 个字母的数字个数优势经典回溯模板逻辑清晰是面试中最推荐的写法解法二队列法BFS思路使用队列进行广度优先搜索BFS。初始队列为空字符串逐个处理每个数字对于队列中每个已有组合扩展当前数字对应的所有字母。functionletterCombinations(digits){if(!digits||digits.length0)return[];constmap{2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz};letqueue[];for(constdigitofdigits){constlettersmap[digit];constnewQueue[];for(constprefixofqueue){for(constletterofletters){newQueue.push(prefixletter);}}queuenewQueue;}returnqueue;}时间复杂度 / 空间复杂度O(3^m × 4^n) / O(3^m × 4^n)优势BFS 思路适合理解不同的遍历方式劣势需要存储中间结果空间占用略大解法三迭代法循环拼接思路使用循环逐个数字处理每次用当前结果集与当前数字对应的字母列表进行笛卡尔积拼接生成新的结果集。functionletterCombinations(digits){if(!digits||digits.length0)return[];constmap{2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz};letresult[];for(constdigitofdigits){constlettersmap[digit];constnewResult[];for(constprefixofresult){for(constletterofletters){newResult.push(prefixletter);}}resultnewResult;}returnresult;}时间复杂度 / 空间复杂度O(3^m × 4^n) / O(3^m × 4^n)优势代码简洁与 BFS 本质相同劣势与 BFS 类似空间占用略大解法对比解法时间 / 空间复杂度优势推荐指数回溯法DFSO(3^m × 4^n) / O(m n)递归经典空间最优⭐⭐⭐⭐⭐队列法BFSO(3^m × 4^n) / O(3^m × 4^n)BFS 思路易于理解⭐⭐⭐⭐迭代法O(3^m × 4^n) / O(3^m × 4^n)代码简洁无需递归⭐⭐⭐⭐扩展题括号生成给定n对括号生成所有由n对括号组成的有效组合。组合总和给定一个无重复元素的数组和一个目标数找出所有可以使数字和等于目标数的组合。子集给定一个整数数组返回该数组所有可能的子集幂集。“他山之石可以攻玉。” —— 《诗经·小雅·鹤鸣》关注李耶每天一道面试题一起卷起来