17. 电话号码的字母组合

题目描述

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

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

提示：

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

题解

解法一：迭代

将问题转化为：每增加一个数字，就在之前的结果集中的每个字符串后面加上这个数字对应的字母。

例如 digits = “23”：

1. 当 digits[0] == ‘2’ 时，res = [“a”, “b”, “c”]
2. 当 digits[1] == ‘3’ 时，向res中追加 “def”，得到新的 res’ = [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]

class Solution {
 public:
  std::vector<std::string> letterCombinations(std::string digits) {
    std::vector<std::string> res;
    for (auto dig : digits) {
      res = letComb(dig, res);
    }
    return res;
  }

 private:
  std::vector<std::string> letComb(char dig,
                                  std::vector<std::string>& last_res) {
    std::vector<std::string> res;
    // 遍历当前数字对应的字母
    for (auto ch : cell_map[dig]) {
      // 向上一次结果进行追加，并将追加结果填充到当前的新结果中
      for (auto str : last_res) {
        res.push_back(str + ch);
      }
      if (last_res.size() == 0) {
        res.push_back(std::string(1, ch));
      }
    }
    return res;
  }

  std::unordered_map<char, std::string> cell_map = {
      {'2', "abc"}, {'3', "edf"},  {'4', "ghi"}, {'5', "jkl"},
      {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxzy"}};
};

解法二：回溯

这是一个典型的回溯穷举问题。

每次递归时，将当前数字对应的字母依次加入到当前字符串中，当字符串长度等于 digits 时，将当前字符串加入到结果集中，然后回溯，将当前字符串的最后一个字符删除。

class Solution {
public:
  std::vector<std::string> letterCombinations(std::string digits) {
    std::vector<std::string> res;
    if (digits.size() == 0) {
      return res;
    } else {
      letComb(res, 0, digits);
    }
    return res;
  }

 private:s
  int letComb(std::vector<std::string>& res, int idx, std::string & digits) {
    if (idx == digits.size()) {
      res.push_back(comb);
    } else {
      std::string str = cell_map[digits[idx]];
      for (auto ch : str) {
        comb.push_back(ch);
        letComb(res, idx+1, digits);
        comb.pop_back();
      }
    }
    return 0;
  }

  std::string comb;

  std::unordered_map<char, std::string> cell_map = {
      {'2', "abc"}, {'3', "edf"},  {'4', "ghi"}, {'5', "jkl"},
      {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxzy"}};
};

总结

1. 迭代法注意在遍历完当前 digits[i] 后，需更新原始结果集，在下一次 i+1 迭代中需要使用更新后的结果集进行追加字符；
2. 回溯条件：idx == digits.size()，将当前字符串加入到结果集中。
3. 在将字符串加入结果集后进行回溯，即将字符串的最后一位删除，并加上下一个字符；