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

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

电话号码的字母组合-17 - 图1

示例 1：

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

示例 2：

  1. 输入：digits = ""
  2. 输出：[]

示例 3：

  1. 输入：digits = "2"
  2. 输出：["a","b","c"]

提示：

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

思路

假设输入23，如下图所示：
17-1.png

DFS需要一个边界条件来终止递归，这个边界条件是当前层数等于输入字符串（如23）的长度时就终止递归。

在DFS时怎么遍历节点是一个问题。我们用一个vectir<string> candidate向量来表示当前这一层需要遍历的字符串。string node表示当前节点。string path既表示当前已经遍历的节点，也起到类似visited数组的作用。

代码

  1. class Solution {
  2. public:
  4.     void dfs(vector<string>& candidate, vector<string>& output_list, int level, string path, int top) {
  5.         // 1. Exit condition
  6.         if( level == top ) {
  7.             output_list.push_back( path );
  8.             return;
  9.         }
  11.         // 2. Walk every nodes that not visited
  12.         int len = candidate[level].size();
  13.         string node = candidate[level];
  14.         for(int i = 0; i < len; i++) {
  15.             path.push_back( node[i] );
  16.             dfs( candidate, output_list, level+1, path, top );
  17.             path.pop_back();
  18.         }
  19.     }
  21.     vector<string> letterCombinations(string digits) {
  22.         vector<string> output_list;
  23.         if( digits.size() <= 0 )   return output_list;
  25.         string path;
  26.         vector<string> keyboard = {
  27.             "",
  28.             "", "abc", "def",
  29.             "ghi", "jkl", "mno",
  30.             "pqrs", "tuv", "wxyz"
  31.         };
  32.         vector<string> candidate;
  33.         for(int i = 0; i < digits.size(); i++) {
  34.             candidate.push_back( keyboard[ digits[i]-'0' ] );
  35.         }
  37.         dfs(candidate, output_list, 0, path, digits.size());
  39.         return output_list;
  40.     }
  41. };