【每日算法】LeetCode 17. 电话号码的字母组合

对前端开发者而言，学习算法绝非为了“炫技”。它是你从"页面构建者"迈向"复杂系统设计者"的关键阶梯。它将你的编码能力从"实现功能"提升到"设计优雅、高效解决方案"的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 17. 电话号码的字母组合

1. 题目描述

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

数字到字母的映射如下（与电话按键相同）：

2: "abc" 3: "def" 4: "ghi" 5: "jkl" 6: "mno" 7: "pqrs" 8: "tuv" 9: "wxyz"

注意：1和0不包含任何字母。

示例 1：

输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = "" 输出：[]

示例 3：

输入：digits = "2" 输出：["a","b","c"]

2. 问题分析

2.1 问题本质

这是一个典型的组合问题，需要找出所有可能的字母排列组合。每个数字对应3-4个字母，我们需要从每个数字对应的字母集合中选取一个字母，然后将所有选出的字母按顺序组合起来。

2.2 关键特征

1. 组合而非排列：顺序是固定的（按输入数字顺序），我们只需要在每个位置选择合适的字母
2. 多重循环的变体：相当于多个for循环的嵌套，但循环层数由输入字符串长度决定
3. 树形结构：可以看作一个树形遍历问题，每个节点代表一个数字，分支代表该数字对应的字母

2.3 前端视角

在前端开发中，类似的问题场景包括：

• 动态表单生成（根据用户选择动态生成下一级选项）
• 路由权限组合（不同权限组合对应不同的可访问路由）
• 商品属性组合（如颜色、尺寸的不同组合）

3. 解题思路

3.1 核心思想：回溯算法

回溯算法是解决组合问题的经典方法，特别适合解决"所有可能"的问题。它通过探索所有可能的路径，并在遇到不可能的情况时回退到上一步。

3.2 算法步骤

1. 建立数字到字母的映射表
2. 如果输入字符串为空，直接返回空数组
3. 初始化结果数组和当前路径
4. 使用深度优先搜索（DFS）回溯：
   • 终止条件：当前路径长度等于输入数字字符串长度
   • 递归过程：获取当前数字对应的字母，遍历每个字母，将其加入路径，递归处理下一个数字，然后回溯（移除路径最后一个字母）

3.3 复杂度分析

• 时间复杂度：O(3^m × 4^n)，其中 m 是输入中对应3个字母的数字个数，n 是输入中对应4个字母的数字个数
• 空间复杂度：O(m+n)，递归调用栈的深度最大为输入数字的长度

3.4 最优解

回溯算法是这个问题的最优解，因为：

1. 必须遍历所有可能的组合才能得到完整答案
2. 避免了不必要的重复计算
3. 空间复杂度相对较低，只存储当前路径和结果

4. 各思路代码实现

4.1 回溯算法（递归实现）

/** * 方法一：经典回溯算法（递归） * @param {string} digits * @return {string[]} */constletterCombinations=function(digits){if(!digits||digits.length===0)return[];// 数字到字母的映射constdigitMap={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};constresult=[];/** * 回溯函数 * @param {number} index - 当前处理的数字索引 * @param {string} current - 当前组合字符串 */constbacktrack=(index,current)=>{// 终止条件：当前组合长度等于输入数字长度if(index===digits.length){result.push(current);return;}// 获取当前数字对应的字母constdigit=digits[index];constletters=digitMap[digit];// 遍历当前数字对应的所有字母for(leti=0;i<letters.length;i++){// 做出选择：添加当前字母到组合中backtrack(index+1,current+letters[i]);// 回溯：在递归返回后，current不变，无需显式移除字符}};backtrack(0,'');returnresult;};

4.2 迭代法（队列实现）

/** * 方法二：迭代法（使用队列） * @param {string} digits * @return {string[]} */constletterCombinationsQueue=function(digits){if(!digits||digits.length===0)return[];constdigitMap={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};// 使用队列存储中间结果letqueue=[''];for(leti=0;i<digits.length;i++){constdigit=digits[i];constletters=digitMap[digit];constqueueLength=queue.length;// 处理队列中现有的所有组合for(letj=0;j<queueLength;j++){constcurrent=queue.shift();// 取出队首元素// 为当前组合添加新的字母for(letk=0;k<letters.length;k++){queue.push(current+letters[k]);}}}returnqueue;};

4.3 函数式编程实现

/** * 方法三：函数式编程实现 * @param {string} digits * @return {string[]} */constletterCombinationsFP=function(digits){if(!digits||digits.length===0)return[];constdigitMap={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};// 使用reduce逐步构建所有组合returndigits.split('').reduce((acc,digit)=>{constletters=digitMap[digit];if(acc.length===0){returnletters.split('');}// 将现有组合与新的字母进行笛卡尔积returnacc.flatMap(comb=>letters.split('').map(letter=>comb+letter));},[]);};

5. 各实现思路的复杂度、优缺点对比

6. 总结

6.1 算法核心要点

1. 回溯算法是解决组合问题的利器，特别适合需要探索所有可能解的场景
2. 递归与迭代可以相互转换，根据具体情况选择合适的方法
3. 剪枝优化：虽然本题无法剪枝（需要所有组合），但在其他问题中可以通过条件判断提前终止无效分支

6.2 前端实际应用场景

场景一：动态表单生成器

// 根据用户选择的选项动态生成下一级选项// 例如：选择省份 -> 选择城市 -> 选择区域functiongenerateFormCombinations(selections){// 类似电话号码组合，每个选择点对应多个选项// 生成所有可能的表单路径}

场景二：路由权限组合

// 用户可能有多种角色，每种角色对应不同的权限// 计算用户可以访问的所有路由组合functiongetAllowedRoutes(userRoles){// 每个角色对应一组可访问路由// 组合所有角色的路由权限}

场景三：商品SKU组合

// 电商平台中，商品可能有多个属性（颜色、尺寸等）// 生成所有可能的SKU组合functiongenerateProductSKUs(attributes){// 例如：颜色：红、蓝；尺寸：S、M、L// 生成：红-S、红-M、红-L、蓝-S、蓝-M、蓝-L}

场景四：国际化文案组合

// 多语言网站中，根据语言和地区组合生成完整的文案路径functiongetI18nPaths(languages,regions){// 例如：语言：en, zh；地区：US, CN// 生成：en-US, en-CN, zh-US, zh-CN}