HHot 100C++ 图解

17. 电话号码的字母组合

一句话套路多叉树按数字逐层展开

题目描述

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

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

 

示例 1:

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

示例 2:

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

 

提示:

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

思路

时间O(4^n · n)(4 来自 7/9 键有 4 个字母)
空间O(n)

思路

多叉树,第 i 层就是第 i 个数字的按键表,逐层展开。

易错

输入 "" 必须返回 [](不是 [""])—— 这是本题唯一的坑。

图解

a 0 d 1
字符串 ad(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/10_backtracking.cpp27 行
namespace lc0017 {
class Solution {
 public:
  vector<string> letterCombinations(string digits) {
    vector<string> ans;
    if (digits.empty()) return ans;
    dfs(digits, 0, "", ans);
    return ans;
  }

 private:
  static const vector<string>& keys() {
    static const vector<string> k{"",    "", "abc", "def", "ghi", "jkl",
                                 "mno", "pqrs", "tuv", "wxyz"};
    return k;
  }

  static void dfs(const string& digits, int idx, const string& path, vector<string>& ans) {
    if (idx == (int)digits.size()) {
      ans.push_back(path);
      return;
    }
    for (char c : keys()[digits[idx] - '0'])  // 当前数字对应的每个字母都分支一次
      dfs(digits, idx + 1, path + c, ans);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q17_phone_letters6 行
lc0017::Solution s;
CHECK_EQ(s.letterCombinations("23"),
         vector<string>{"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"});
CHECK_EQ(s.letterCombinations(""), vector<string>{});  // 空输入 != {""}
CHECK_EQ(s.letterCombinations("2"), vector<string>{"a", "b", "c"});
CHECK_EQ(s.letterCombinations("79").size(), (size_t)16);  // 4×4

↑↓ 选择↵ 打开/ 随时唤起