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 4digits[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 ListString letterCombinations(String digits) { if (digits null || digits.length() 0) { return List.of(); } ListString ans new ArrayList(); // 核心开辟一个与输入长度完全一致的固定数组 char[] path new char[digits.length()]; help(0, ans, digits.toCharArray(), path); return ans; } private void help(int i, ListString 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); // 递进到下一层 } } }