17. 电话号码的字母组合

题目

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

数字到字母的映射方式与电话按键相同。注意 1 不对应任何字母。

思路

实现思路

采用回溯算法的方式，通过深度优先搜索遍历所有可能的字母组合。使用 StringBuffer 作为临时存储结构，在递归过程中不断添加字符并回溯，生成所有可能的组合。

关键步骤解析

1. 初始化映射关系：创建 String 数组 cs，将数字 2-9 映射到对应的字母字符串。
2. 处理边界情况：如果输入字符串 digits 为空，直接返回 []。
3. 递归处理每一位数字：
   • 使用 depth 参数表示当前处理的数字位置
   • 获取当前数字对应的字母字符串 c1
   • 遍历该字符串中的每个字符，依次尝试添加到组合中
4. 回溯操作：
   • 在递归前将字符添加到 sb 中
   • 递归处理下一位数字
   • 递归返回后删除最后添加的字符，进行回溯
5. 终止条件：当 sb 的长度等于 digits 的长度时，说明已生成一个完整的字母组合，将其添加到结果集 ans 中。

代码

import java.util.ArrayList;

public class P17 {
   private StringBuffer sb = new StringBuffer();

   public List<String> letterCombinations(String digits) {
      if (digits.isEmpty()) {
         return new ArrayList<>();
      }
      String[] cs = new String[10];
      cs[2] = "abc";
      cs[3] = "def";
      cs[4] = "ghi";
      cs[5] = "jkl";
      cs[6] = "mno";
      cs[7] = "pqrs";
      cs[8] = "tuv";
      cs[9] = "wxyz";
      List<String> ans = new ArrayList<>();
      dfs(digits, 0, ans, cs);
      return ans;
   }

   private void dfs(String digits, int depth, List<String> ans, String[] cs) {
      // 终止条件：当遍历完之后即可
      if (sb.length() == digits.length()) {
         // 满足digits长度才能添加
         ans.add(new String(sb));
         return;
      }

      char c = digits.charAt(depth);
      int num = c - '0';
      String c1 = cs[num];
      // 组合，重复
      for (int i = 0; i < c1.length(); i++) {
         // 先添加，
         sb.append(c1.charAt(i));
         // 递归
         dfs(digits, depth + 1, ans, cs);
         // 回溯
         sb.deleteCharAt(sb.length() - 1);
      }
   }
}

总结

复杂度分析

• 时间复杂度：O(3^m × 4^n)，其中 m 是对应字母数为 3 的数字个数，n 是对应字母数为 4 的数字个数。最坏情况下所有数字都对应 4 个字母。
• 空间复杂度：O(m + n)，递归调用栈的最大深度为数字字符串的长度，sb 最多存储 m + n 个字符。

核心特点

通过回溯算法遍历所有可能的字母组合情况，利用 StringBuffer 的可变性提高字符串操作效率。算法结构清晰，易于理解和实现，适用于处理类似组合问题。