电话号码的字母组合

约 1355 字大约 5 分钟

2025-03-02

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'] 的一个数字。

回溯

先遍历数字，再遍历数字对应的字母。无重不可复选固定长度的组合。分段遍历。一个数字对应一段字母。

class Solution {
    // 每个数字到字母的映射
    String[] mapping = new String[] {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    List<String> res = new LinkedList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return res;
        }
        // 从 digits[0] 开始进行回溯
        backtrack(digits, 0, new StringBuilder());
        return res;
    }

    // 回溯算法主函数
    void backtrack(String digits, int start, StringBuilder sb) {
        if (sb.length() == digits.length()) {
            // 到达回溯树底部
            res.add(sb.toString());
            return;
        }
        
        // 回溯算法框架
        // 第一个 for 循环是遍历 digits，digits中的i决定了下一次回溯从第几层开始，比如第一层的节点是2，第二层的节点是3。
        // 第二个for循环遍历的是每个节点下的树枝，在第一个for循环确定了第几层节点后，第二个for循环就开始遍历该节点下的树枝。
        // 以23为例，先遍历2，再遍历2对应的字符a、b、c。
        for (int i = start; i < digits.length(); i++) {
            int digit = digits.charAt(i) - '0';
            for (char c : mapping[digit].toCharArray()) {
                // 做选择
                sb.append(c);
                // 递归下一层回溯树
                backtrack(digits, i + 1, sb);
                // 撤销选择
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}

时间复杂度： $O\left(3^m \times 4^n\right)$ ，即组合总数，其中 $m$ 是输入中对应 3 个字母的数字个数（包括数字 $2$ 、 $3$ 、4、 $5$ 、 $6$ 、 $8$ )， $n$ 是输入中对应 4 个字母的数字个数（包括数字 7、9）， $m+n$ 是输入数字的总个数。当输入包含 $m$ 个对应 3 个字母的数字和 $n$ 个对应 4 个字母的数字时，不同的字母组合一共有 $3^m \times 4^n$ 种，需要遍历每一种字母组合。
空间复杂度： $O(m+n)$ ，其中 $m$ 是输入中对应 3 个字母的数字个数， $n$ 是输入中对应 4 个字母的数字个数， $m+n$ 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 $m+n$ 。

BFS

计算出队列长度后，将队列中的每个元素挨个拿出来，假设队列中的元素是a，b，c，先取a，分别和d，e，f拼接，得到ad，ae，af，放入队列，此时队列是b，c，ad，ae，af。有点类似BFS

第一个 for 循环遍历所有的数字，第二个for循环遍历队列，第三个for循环遍历第一个for循环确定的数字对应的字母。和BFS有点类似，即都是一边取一边加，不同的是BFS的加是依赖于数据结构，即树的指针，而这里的加依赖于第一个和第三个for循环。

假设 digits = "23"，我们需要找出所有可能的字母组合。

代码执行过程

digits = "23"
初始化 res 为 [""]
处理数字 '2'，结果为 ["a", "b", "c"]
处理数字 '3'，结果为 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

最终输出所有可能的字母组合。

class Solution {
	public List<String> letterCombinations(String digits) {
		if(digits == null || digits.length() == 0) {
			return new ArrayList<String>();
		}
		
		//一个映射表，第二个位置是"abc“,第三个位置是"def"。。。
		//这里也可以用map，用数组可以更节省点内存
		String[] letter_map = {
			" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
		};
		List<String> res = new ArrayList<>();
		
		//先往队列中加入一个空字符
		res.add("");
		for (int i = 0; i < digits.length(); i++) {
			// 由当前遍历到的字符，取字典表中查找对应的字符串
			String letters = letter_map[digits.charAt(i) - '0'];
			int size = res.size();
			// 计算出队列长度后，将队列中的每个元素挨个拿出来，
			// 假设队列中的元素是a，b，c，先取a，分别和d，e，f拼接，得到ad，ae，af，放入队列，此时队列是b，c，ad，ae，af
			// 可以先遍历队列中已有的数字，再遍历选择，也可以先遍历选择，再遍历已有数字。
			for (int j = 0; j < size; j++) {
			    // 假设每个数字对应的字符都是4个，i=1时，size=4，i=2时，size=16，……，i=n-1时，size=4^{n-1}。
			    // letters的长度一直是4，所以两个for循环的时间复杂度是 4*4+4^2*4+...+4^{n-1}*4=4^2+...+4^n=O(4^n)。
			    // 队列里最多有4^n个字符串，每个字符串的长度是n，所以空间复杂度是O(n*4^n)。
				// 每次都从队列中拿出第一个元素
				String tmp = res.remove(0);
				// 然后跟"def"这样的字符串拼接，并再次放到队列中
				for (int k = 0; k < letters.length(); k++) {
					res.add(tmp + letters.charAt(k));
				}
			}
		}
		return res;
	}
}