算法面试：如何求解数字键盘的字母组合问题

在经典的技术面试中，将数字映射到特定字符集，并求解所有可能的字母组合，是一个考察递归与回溯基础的高频题。

问题本质

给定一个仅包含数字 2-9 的字符串，输出该数字序列能够组成的所有字母组合。数字到字母的映射关系与标准电话按键一致，例如 2 对应 a、b、c，3 对应 d、e、f。

核心解题思路：回溯算法

组合长度由输入数字的个数决定，每一位数字又对应多个分支选择。这天然适合使用深度优先搜索与回溯。

算法步骤

• 构建映射表，将字符 2 到 9 与对应字母字符串绑定。
• 使用一个指针记录当前处理到的数字下标。
• 当指针到达输入字符串末尾时，将当前组合写入结果集。
• 对当前数字的每个候选字母，先加入路径，再递归处理下一位。
• 递归返回后移除最后一个字母，继续尝试下一个候选字母。

复杂度分析

时间复杂度为 O(4^N * N)，其中 N 是输入字符串长度。某些数字如 7 和 9 对应 4 个字母，因此最坏情况下分支数会快速增长。

空间复杂度为 O(N)，主要来自递归调用栈和当前路径。