Medium

题目描述

给定一个仅包含数字 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'] 的一个数字。

解题思路

解题思路

这是一个经典的回溯（Backtracking）问题。我们需要遍历所有可能的字母组合。

核心思想：

  1. 建立映射：首先建立数字到字母的映射关系，如数字2对应"abc"，数字3对应"def"等
  2. 回溯搜索：使用深度优先搜索（DFS）的方式，对每个数字位置尝试所有可能的字母
  3. 状态管理：维护当前已构建的字符串，当长度等于输入数字串长度时，说明找到一个完整组合

算法步骤：

  1. 特殊情况处理：如果输入为空，直接返回空列表
  2. 定义数字到字母的映射表
  3. 使用回溯函数，参数包括当前构建的字符串和当前处理的数字索引
  4. 对于当前数字，尝试其对应的每个字母，递归处理下一个数字
  5. 当处理完所有数字时，将当前字符串加入结果集

这种方法的优势是思路清晰，代码简洁，时间复杂度最优。

代码实现

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        
        vector<string> mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result;
        string current;
        
        backtrack(digits, 0, current, mapping, result);
        return result;
    }
    
private:
    void backtrack(const string& digits, int index, string& current, 
                   const vector<string>& mapping, vector<string>& result) {
        if (index == digits.length()) {
            result.push_back(current);
            return;
        }
        
        int digit = digits[index] - '0';
        for (char c : mapping[digit]) {
            current.push_back(c);
            backtrack(digits, index + 1, current, mapping, result);
            current.pop_back();
        }
    }
};

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        mapping = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
        
        result = []
        
        def backtrack(index, current):
            if index == len(digits):
                result.append(current)
                return
            
            digit = digits[index]
            for letter in mapping[digit]:
                backtrack(index + 1, current + letter)
        
        backtrack(0, "")
        return result

public class Solution {
    public IList<string> LetterCombinations(string digits) {
        if (string.IsNullOrEmpty(digits)) return new List<string>();
        
        var mapping = new Dictionary<char, string> {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        
        var result = new List<string>();
        
        void Backtrack(int index, string current) {
            if (index == digits.Length) {
                result.Add(current);
                return;
            }
            
            char digit = digits[index];
            foreach (char letter in mapping[digit]) {
                Backtrack(index + 1, current + letter);
            }
        }
        
        Backtrack(0, "");
        return result;
    }
}

var letterCombinations = function(digits) {
    if (digits.length === 0) return [];
    
    const map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    };
    
    const result = [];
    
    function backtrack(index, current) {
        if (index === digits.length) {
            result.push(current);
            return;
        }
        
        const letters = map[digits[index]];
        for (let letter of letters) {
            backtrack(index + 1, current + letter);
        }
    }
    
    backtrack(0, '');
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(3^m × 4^n)，其中 m 是对应 3 个字母的数字个数，n 是对应 4 个字母的数字个数。最坏情况下每个数字对应 4 个字母，总共 4^4 种组合
空间复杂度O(3^m × 4^n)，递归调用栈深度为输入字符串长度，结果存储空间与组合总数成正比

相关题目