leetcode：17. 电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
[中等] 17. 电话号码的字母组合 - 图1

示例：

  1. 输入：digits = "23"
  2. 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
  1. 输入：digits = ""
  2. 输出：[]
  1. 输入：digits = "2"
  2. 输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

解答 & 代码

递归回溯：

  1. class Solution {
  2. private:
  3.       // 存储每个数字可能对应的字母, eg. phoneMap[2]="abc"，代表数字2可能对应字母a、b、c
  4.     vector<string> phoneMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  5.     vector<string> resultList;    // 结果数组
  6.     string result;                            // 一种可能的排列组合
  8.       // 递归回溯
  9.     void backTrack(string digits, int idx)
  10.     {
  11.           // 递归结束条件：如果当前遍历 digits 结束（idx 越界），则将当前的字母组合 result 存入 resultList
  12.         if(idx >= digits.size())
  13.         {
  14.             resultList.push_back(result);
  15.             return;
  16.         }
  18.         int digit = digits[idx] - '0';                // 当前遍历到的数字
  19.         string candidates = phoneMap[digit];    // 当前数字对应的所有候选字母
  20.           // 遍历所有当前数字的所有候选字母
  21.         for(int i = 0; i < candidates.size(); ++i)
  22.         {
  23.             result.push_back(candidates[i]);    // 将该字母插入 result 尾部
  24.             backTrack(digits, idx + 1);                // 递归处理下一个数字
  25.             result.pop_back();                                // 回溯，撤销改动
  26.         }
  27.     }
  28. public:
  29.     vector<string> letterCombinations(string digits) {
  30.         if(digits.size() > 0)
  31.             backTrack(digits, 0);
  32.         return resultList;
  33.     }
  34. };

复杂度分析：设电话号码共有 n 个数字（其中 i 个数字对应 3 个字符，j 个数字对应 4 个字符）

  • 时间复杂度 [中等] 17. 电话号码的字母组合 - 图2
  • 空间复杂度 O(n) = O(i + j)：
    • 递归调用层数 n，空间复杂度 O(n)
    • phoneMap的空间复杂度算 O(1)，因为是存储了固定的 26 个字母

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.3 MB, 在所有 C++ 提交中击败了 79.21% 的用户