以下是 LeetCode 第 17 题「电话号码的字母组合」的 Java 实现采用 回溯Backtracking 的经典解法解题思路1. 建立映射用 String[] 或 Map 存储每个数字对应的字母2. 回溯递归逐个数字遍历将每个数字对应的所有字母依次加入当前路径3. 终止条件当路径长度等于输入数字串长度时将当前组合加入结果集4. 回溯撤销递归返回后移除最后一个加入的字母尝试下一个分支Java 代码javaimport java.util.ArrayList;import java.util.List;class Solution {// 数字到字母的映射表2-9private static final String[] PHONE_MAP {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz // 9};private ListString result;private StringBuilder current;private String digits;public ListString letterCombinations(String digits) {result new ArrayList();// 边界情况空字符串if (digits null || digits.length() 0) {return result;}this.digits digits;this.current new StringBuilder();// 从第 0 个数字开始回溯backtrack(0);return result;}/*** 回溯函数* param index 当前处理到 digits 的第几个数字*/private void backtrack(int index) {// 终止条件所有数字都处理完毕if (index digits.length()) {result.add(current.toString());return;}// 获取当前数字对应的字母串int digit digits.charAt(index) - 0;String letters PHONE_MAP[digit];// 遍历当前数字对应的所有字母for (int i 0; i letters.length(); i) {// 做选择将当前字母加入路径current.append(letters.charAt(i));// 递归处理下一个数字backtrack(index 1);// 撤销选择回溯移除最后一个字母current.deleteCharAt(current.length() - 1);}}}复杂度分析指标 复杂度 说明时间复杂度 O(3ⁿ × 4ᵐ) n 是映射到 3 个字母的数字个数2-6,8m 是映射到 4 个字母的数字个数7,9每个数字的字母都要组合空间复杂度 O(n) 递归栈深度为 n数字串长度加上存储当前路径的 StringBuilder示例验证- 输入digits 23- 数字映射2 → abc3 → def- 回溯过程/ | \a b c/|\ /|\ /|\d e f d e f d e f- 输出[ad,ae,af,bd,be,bf,cd,ce,cf]迭代版本BFS 队列实现如果你更习惯迭代而非递归也可以用队列实现javaimport java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;class Solution {private static final String[] PHONE_MAP {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};public ListString letterCombinations(String digits) {ListString result new ArrayList();if (digits null || digits.length() 0) {return result;}// 用队列模拟 BFSQueueString queue new LinkedList();queue.offer();for (int i 0; i digits.length(); i) {int size queue.size();String letters PHONE_MAP[digits.charAt(i) - 0];for (int j 0; j size; j) {String prefix queue.poll();for (char c : letters.toCharArray()) {queue.offer(prefix c);}}}result.addAll(queue);return result;}}两种实现对比实现方式 特点 适用场景回溯递归 代码清晰空间复杂度低 一般推荐BFS迭代 避免递归栈溢出但空间占用大 数字串很长时更安全回溯版本是面试中最常写、最推荐的实现方式。