hot100 电话号码的字母组合(17)

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

回溯可解

时间: o(n * 4的n次方) n是输入字符串的长度

空间: o(n)

class Solution { private static final String[] MAPPING = new String[]{ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return List.of(); } List<String> ans = new ArrayList<>(); // 核心：开辟一个与输入长度完全一致的固定数组 char[] path = new char[digits.length()]; help(0, ans, digits.toCharArray(), path); return ans; } private void help(int i, List<String> ans, char[] digits, char[] path) { // 边界条件：递归深度达到数字长度，说明路径已填满 if (i == digits.length) { ans.add(new String(path)); // 导出结果 return; } String letters = MAPPING[digits[i] - '0']; for (char letter : letters.toCharArray()) { path[i] = letter; // 原地覆盖，无需显式 remove help(i + 1, ans, digits, path); // 递进到下一层 } } }