本文共 3733 字，大约阅读时间需要 12 分钟。

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

题意：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。注意 1 不对应任何字母。

思路1：就是这些数字字符对应的字母集的笛卡尔积。我们用简单的DFS+回溯即可解决。以 digits = "23" 为例，它对应的解空间树如下，从根结点到叶子结点的每一条路径都是一个字母组合：

• digits 是一个数字字符串；
• s(digits) 是 digits 所能代表的字母字符串；
• letter(digits[i]) 是 digits[i] 对应的几个字母之一；
• s(digits[0...n-1]) = letter(digits[0]) + s(digits[1...n-1]) = letter(digits[0]) + letter[digits[1]) + s(digits[2...n-1]) = ...

先序实现的代码如下，到达叶子结点时将字符组合加入到字符串数组 ans 中：

class Solution {
   public:    unordered_map
   
     dict = {
           {
   '2', "abc"}, {
   '3', "def"}, {
   '4', "ghi"},         {
   '5', "jkl"}, {
   '6', "mno"}, {
   '7', "pqrs"},         {
   '8', "tuv"}, {
   '9', "wxyz"}    };    vector
    
      ans;    //s中保存了此时从digits[0...idx-1]翻译得到的一个字母字符串    //寻找和digits[idx]匹配的字母,获得digits[0...idx]翻译的解    void dfs(const string &s, const string &digits, int idx) {
           if (idx == digits.size()) {
               ans.push_back(s);            return;        }        const string &t = dict[digits[idx]];        for (char c : t)             dfs(s + c, digits, idx + 1);    }    vector
     
       letterCombinations(string digits) {
           if (digits.empty()) return ans;        dfs("", digits, 0);         return ans;    }};
     
    
   

效率如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：6.5 MB, 在所有 C++ 提交中击败了96.46% 的用户

后序实现的代码如下，递归基准是：递归到叶子结点时返回对应的字符；递归体：在函数返回的所有字符串之前，添加当前 digits[i] 对应的字符。

class Solution {
   public:    const string letterMap[10] = {
   " ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};      vector
   
     letterCombinations(const string &digits, int idx) {
           vector
    
      res;        //递归边界条件(只有空串时可能用到)        if (idx >= digits.size()) return res;        char c = digits[idx];        assert(c >= '0' && c <= '9' && c != '1');        const string &letters = letterMap[c - '0'];        //递归边界条件        if (idx == digits.size() - 1) {
               for (char ch : letters)                res.emplace_back(1, ch);            return res;         }        //递归体        vector
     
       postfix = letterCombinations(digits, idx + 1);        for (char ch : letters)             for (const string &s : postfix)                 res.push_back(string(1, ch) + s);        return res;    }     vector
      
        letterCombinations(string digits) {
            return letterCombinations(digits, 0);    }};
      
     
    
   

效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了49.75% 的用户内存消耗：6.8 MB, 在所有 C++ 提交中击败了28.13% 的用户

思路2：Python可以用列表推导，使用循环解决这道题。C++也可以用循环，只是需要在循环中修改 ans 数组。代码如下：

class Solution {
   public:    unordered_map
   
     dict = {
           {
   '2', "abc"}, {
   '3', "def"}, {
   '4', "ghi"},         {
   '5', "jkl"}, {
   '6', "mno"}, {
   '7', "pqrs"},         {
   '8', "tuv"}, {
   '9', "wxyz"}    };     vector
    
      letterCombinations(string digits) {
           if (digits.empty()) return vector
     
      ();         vector
      
        ans(1, ""), tmp;        int j = 0;        for (char c : digits) {
                tmp.clear();            for (const string &pre : ans) {
                    const string &t = dict[c];                for (char ch : t)                     tmp.push_back(pre + ch);             }            ans = tmp;        }        return ans;    }};
      
     
    
   

效率较低：

执行用时：4 ms, 在所有 C++ 提交中击败了48.75% 的用户内存消耗：6.9 MB, 在所有 C++ 提交中击败了19.08% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108251121 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！